华为OD机试 2025B卷 - 小明减肥(C++&Python&JAVA&JS&C语言)

2025B卷目录点击查看： 华为OD机试2025B卷真题题库目录｜机考题库 + 算法考点详解

2025B卷 100分题型

最新华为OD机试

真题目录：点击查看目录
华为OD面试真题精选：点击立即查看

题目描述

小明有n个可选运动，每个运动有对应卡路里，想选出其中k个运动且卡路里和为t。k，t，n都是给定的。求出可行解数量

输入描述

第一行输入 n t k

第一行输入 每个运动的卡路里 按照空格进行分割

备注

• 0 < n < 10
• t > 0, 0 < k <= n
• 每个运动量的卡路里 > 0

输出描述

求出可行解数量

示例1

输入

4 3 2
1 1 2 3

输出

2

说明

可行解为2，选取{0, 2}, {1,2}两种方式。

解题思路

暴力回溯

这个问题的核心目标是选出 k 个运动，使得它们的卡路里总和恰好是 t。由于运动的数量 n 较小（0 < n < 10），我们可以利用回溯（Backtracking）算法来穷举所有可能的组合，从中找到符合条件的组合。

回溯函数 backtrack:

• 函数接受当前的运动索引 index，还需要选择的运动数量 k，以及目标卡路里 t 和当前已经选取的卡路里和 currentSum 以及已选运动的数量 count。
• 终止条件:
  • 如果已经选出了 k 个运动且它们的卡路里和正好等于 t，则找到一种有效组合，返回 1。
  • 如果当前运动超出数组边界，或已选运动数量达到了 k，或当前的卡路里和超过了 t，则返回 0，表示这一条路径不再有效。
• 递归选择:
  • 选择当前运动并递归继续寻找其他运动，更新当前总和和已选数量。
  • 不选择当前运动，则直接递归查找下一个运动。
• 最后将两种选择的结果相加，返回总的有效组合数。

动态规划

这个问题还可以通过动态规划来解决，目标是找到选择k个运动使得卡路里总和为t的不同组合数量。思路如下：

解题思路

1. 定义状态：

   • 设dp[j][m]表示选择j个运动，卡路里总和为m的组合数量。

2. 初始化状态：

   • dp[0][0] = 1，因为选择0个运动使得卡路里和为0的方式只有一种，即什么都不选择。
   • 其他状态dp[j][m]初始化为0，因为在未填充前没有任何组合。

3. 状态转移方程：

   • 对于每一个运动的卡路里值cal，我们从后往前遍历选择数量j（从k到1）和卡路里总和m（从t到cal）。
   • 转移方程为：
     • dp[j][m] += dp[j-1][m-cal]
   • 这个公式的意思是：如果当前选择的运动卡路里是cal，那么要使得选择j个运动且卡路里为m，我们需要在之前的组合中选择j-1个运动，其卡路里和为m-cal。

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入：n, t, k
        String[] firstLine = scanner.nextLine().trim().split(" ");
        int n = Integer.parseInt(firstLine[0]); // 运动数量
        int t = Integer.parseInt(firstLine[1]); // 目标卡路里
        int k = Integer.parseInt(firstLine[2]); // 需要选择的运动数量
        
        // 读取每个运动的卡路里
        String[] secondLine = scanner.nextLine().trim().split(" ");
        int[] calories = new int[n];
        for (int i = 0; i < n; i++) {
            calories[i] = Integer.parseInt(secondLine[i]);
        }
        
        // 使用回溯法求解
        int result = backtrack(calories, 0, k, t, 0, 0);
        System.out.println(result);
        
        scanner.close();
    }
    
    /**
     * 回溯法计算符合条件的解决方案数量
     * @param calories 卡路里数组
     * @param index 当前考虑的运动索引
     * @param k 还需要选择的运动数量
     * @param t 目标卡路里
     * @param currentSum 当前已选运动的卡路里和
     * @param count 已选择的运动数量
     * @return 符合条件的方案数
     */
    private static int backtrack(int[] calories, int index, int k, int t, int currentSum, int count) {
        // 如果已经选择了k个运动且卡路里和为t，找到一种方案
        if (count == k && currentSum == t) {
            return 1;
        }
        
        // 如果运动已经考虑完，或者已经选了k个运动，或者当前和已经超过t，无法构成有效方案
        if (index == calories.length || count == k || currentSum > t) {
            return 0;
        }
        
        // 选择当前运动
        int pickCurrent = backtrack(calories, index + 1, k, t, currentSum + calories[index], count + 1);
        
        // 不选择当前运动
        int skipCurrent = backtrack(calories, index + 1, k, t, currentSum, count);
        
        // 返回两种选择的总方案数
        return pickCurrent + skipCurrent;
    }
}



import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入：n, t, k
        String[] firstLine = scanner.nextLine().trim().split(" ");
        int n = Integer.parseInt(firstLine[0]); // 运动数量
        int t = Integer.parseInt(firstLine[1]); // 目标卡路里
        int k = Integer.parseInt(firstLine[2]); // 需要选择的运动数量
        
        // 读取每个运动的卡路里
        String[] secondLine = scanner.nextLine().trim().split(" ");
        int[] calories = new int[n];
        for (int i = 0; i < n; i++) {
            calories[i] = Integer.parseInt(secondLine[i]);
        }
        
        // 创建二维DP数组
        // dp[j][m] 表示选择j个运动，总卡路里为m的方案数
        int[][] dp = new int[k+1][t+1];
        
        // 初始化：选0个运动，卡路里为0的方案数为1
        dp[0][0] = 1;
        
        // 填充DP表格
        for (int i = 0; i < n; i++) {
            int cal = calories[i]; // 当前运动的卡路里
            
            // 需要从后往前遍历，避免重复计算
            for (int j = k; j >= 1; j--) {
                for (int m = t; m >= cal; m--) {
                    dp[j][m] += dp[j-1][m-cal];
                }
            }
        }
        
        System.out.println(dp[k][t]);
        
        scanner.close();
    }
}

Python

def backtrack(calories, index, k, t, current_sum, count):
    """
    回溯法计算符合条件的解决方案数量
    
    参数:
    calories -- 卡路里数组
    index -- 当前考虑的运动索引
    k -- 还需要选择的运动数量
    t -- 目标卡路里
    current_sum -- 当前已选运动的卡路里和
    count -- 已选择的运动数量
    
    返回:
    符合条件的方案数
    """
    # 如果已经选择了k个运动且卡路里和为t，找到一种方案
    if count == k and current_sum == t:
        return 1
    
    # 如果运动已经考虑完，或者已经选了k个运动，或者当前和已经超过t，无法构成有效方案
    if index == len(calories) or count == k or current_sum > t:
        return 0
    
    # 选择当前运动
    pick_current = backtrack(calories, index + 1, k, t, current_sum + calories[index], count + 1)
    
    # 不选择当前运动
    skip_current = backtrack(calories, index + 1, k, t, current_sum, count)
    
    # 返回两种选择的总方案数
    return pick_current + skip_current


first_line = input().strip().split()
n = int(first_line[0])  # 运动数量
t = int(first_line[1])  # 目标卡路里
k = int(first_line[2])  # 需要选择的运动数量

# 读取每个运动的卡路里
calories = list(map(int, input().strip().split()))

# 使用回溯法求解
result = backtrack(calories, 0, k, t, 0, 0)
print(result)

    
    
    
    
    
    
    
    
    
    
# 读取输入：n, t, k
first_line = input().strip().split()
n = int(first_line[0])  # 运动数量
t = int(first_line[1])  # 目标卡路里
k = int(first_line[2])  # 需要选择的运动数量

# 读取每个运动的卡路里
second_line = input().strip().split()
calories = [0] * n
for i in range(n):
    calories[i] = int(second_line[i])

# 创建二维DP数组
# dp[j][m] 表示选择j个运动，总卡路里为m的方案数
dp = [[0] * (t + 1) for _ in range(k + 1)]

# 初始化：选0个运动，卡路里为0的方案数为1
dp[0][0] = 1

# 填充DP表格
for i in range(n):
    cal = calories[i]  # 当前运动的卡路里

    # 需要从后往前遍历，避免重复计算
    for j in range(k, 0, -1):
        for m in range(t, cal - 1, -1):
            dp[j][m] += dp[j-1][m-cal]

print(dp[k][t])
 

JavaScript

// 引入readline模块处理标准输入
const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let lines = [];

// 监听行输入事件
rl.on('line', (line) => {
  lines.push(line);
  
  // 当收集到2行输入时，进行处理
  if (lines.length === 2) {
    // 解析第一行输入：n, t, k
    const [n, t, k] = lines[0].trim().split(' ').map(Number);
    
    // 解析第二行输入：每个运动的卡路里
    const calories = lines[1].trim().split(' ').map(Number);
    
    // 使用回溯法求解
    const result = backtrack(calories, 0, k, t, 0, 0);
    console.log(result);
    
    // 关闭输入流
    rl.close();
  }
});

/**
 * 回溯法计算符合条件的解决方案数量
 * @param {number[]} calories - 卡路里数组
 * @param {number} index - 当前考虑的运动索引
 * @param {number} k - 还需要选择的运动数量
 * @param {number} t - 目标卡路里
 * @param {number} currentSum - 当前已选运动的卡路里和
 * @param {number} count - 已选择的运动数量
 * @returns {number} - 符合条件的方案数
 */
function backtrack(calories, index, k, t, currentSum, count) {
  // 如果已经选择了k个运动且卡路里和为t，找到一种方案
  if (count === k && currentSum === t) {
    return 1;
  }
  
  // 如果运动已经考虑完，或者已经选了k个运动，或者当前和已经超过t，无法构成有效方案
  if (index === calories.length || count === k || currentSum > t) {
    return 0;
  }
  
  // 选择当前运动
  const pickCurrent = backtrack(calories, index + 1, k, t, currentSum + calories[index], count + 1);
  
  // 不选择当前运动
  const skipCurrent = backtrack(calories, index + 1, k, t, currentSum, count);
  
  // 返回两种选择的总方案数
  return pickCurrent + skipCurrent;
}





// 引入readline模块处理标准输入
const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let lines = [];

// 监听行输入事件
rl.on('line', (line) => {
  lines.push(line);
  
  // 当收集到2行输入时，进行处理
  if (lines.length === 2) {
    // 解析第一行输入：n, t, k
    const firstLine = lines[0].trim().split(' ');
    const n = parseInt(firstLine[0]); // 运动数量
    const t = parseInt(firstLine[1]); // 目标卡路里
    const k = parseInt(firstLine[2]); // 需要选择的运动数量
    
    // 解析第二行输入：每个运动的卡路里
    const secondLine = lines[1].trim().split(' ');
    const calories = new Array(n);
    for (let i = 0; i < n; i++) {
      calories[i] = parseInt(secondLine[i]);
    }
    
    // 创建二维DP数组
    // dp[j][m] 表示选择j个运动，总卡路里为m的方案数
    const dp = Array(k + 1).fill().map(() => Array(t + 1).fill(0));
    
    // 初始化：选0个运动，卡路里为0的方案数为1
    dp[0][0] = 1;
    
    // 填充DP表格
    for (let i = 0; i < n; i++) {
      const cal = calories[i]; // 当前运动的卡路里
      
      // 需要从后往前遍历，避免重复计算
      for (let j = k; j >= 1; j--) {
        for (let m = t; m >= cal; m--) {
          dp[j][m] += dp[j-1][m-cal];
        }
      }
    }
    
    console.log(dp[k][t]);
    
    // 关闭输入流
    rl.close();
  }
});

C++

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

// 回溯法计算符合条件的解决方案数量
int backtrack(const vector<int>& calories, int index, int k, int t, int currentSum, int count) {
    // 如果已经选择了k个运动且卡路里和为t，找到一种方案
    if (count == k && currentSum == t) {
        return 1;
    }
    
    // 如果运动已经考虑完完，或者已经选了k个运动，或者当前和已经超过t，无法构成有效方案
    if (index == calories.size() || count == k || currentSum > t) {
        return 0;
    }
    
    // 选择当前运动
    int pickCurrent = backtrack(calories, index + 1, k, t, currentSum + calories[index], count + 1);
    
    // 不选择当前运动
    int skipCurrent = backtrack(calories, index + 1, k, t, currentSum, count);
    
    // 返回两种选择的总方案数
    return pickCurrent + skipCurrent;
}

int main() {
    // 读取输入：n, t, k
    int n, t, k;
    cin >> n >> t >> k;

    // 读取每个运动的卡路里
    vector<int> calories(n);
    for (int i = 0; i < n; ++i) {
        cin >> calories[i];
    }

    // 使用回溯法求解
    int result = backtrack(calories, 0, k, t, 0, 0);
    cout << result << endl;

    return 0;
}







#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
int main() {
    // 读取输入：n, t, k
    string firstLine;
    getline(cin, firstLine);
    istringstream iss1(firstLine);
    
    int n, t, k;
    iss1 >> n >> t >> k; // 分别是：运动数量、目标卡路里、需要选择的运动数量
    
    // 读取每个运动的卡路里
    string secondLine;
    getline(cin, secondLine);
    istringstream iss2(secondLine);
    
    vector<int> calories(n);
    for (int i = 0; i < n; i++) {
        iss2 >> calories[i];
    }
    
    // 创建二维DP数组
    // dp[j][m] 表示选择j个运动，总卡路里为m的方案数
    vector<vector<int>> dp(k + 1, vector<int>(t + 1, 0));
    
    // 初始化：选0个运动，卡路里为0的方案数为1
    dp[0][0] = 1;
    
    // 填充DP表格
    for (int i = 0; i < n; i++) {
        int cal = calories[i]; // 当前运动的卡路里
        
        // 需要从后往前遍历，避免重复计算
        for (int j = k; j >= 1; j--) {
            for (int m = t; m >= cal; m--) {
                dp[j][m] += dp[j-1][m-cal];
            }
        }
    }
    
    // 输出结果
    cout << dp[k][t] << endl;
    
    return 0;
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 回溯法计算符合条件的解决方案数量
 * 
 * @param calories 卡路里数组
 * @param index 当前考虑的运动索引
 * @param k 还需要选择的运动数量
 * @param t 目标卡路里
 * @param currentSum 当前已选运动的卡路里和
 * @param count 已选择的运动数量
 * @param n 运动总数
 * @return 符合条件的方案数
 */
int backtrack(int* calories, int index, int k, int t, int currentSum, int count, int n) {
    // 如果已经选择了k个运动且卡路里和为t，找到一种方案
    if (count == k && currentSum == t) {
        return 1;
    }
    
    // 如果运动已经考虑完，或者已经选了k个运动，或者当前和已经超过t，无法构成有效方案
    if (index == n || count == k || currentSum > t) {
        return 0;
    }
    
    // 选择当前运动
    int pickCurrent = backtrack(calories, index + 1, k, t, currentSum + calories[index], count + 1, n);
    
    // 不选择当前运动
    int skipCurrent = backtrack(calories, index + 1, k, t, currentSum, count, n);
    
    // 返回两种选择的总方案数
    return pickCurrent + skipCurrent;
}

int main() {
    int n, t, k;
    
    // 读取输入：n, t, k
    scanf("%d %d %d", &n, &t, &k);
    
    // 创建并读取每个运动的卡路里
    int* calories = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &calories[i]);
    }
    
    // 使用回溯法求解
    int result = backtrack(calories, 0, k, t, 0, 0, n);
    printf("%d\n", result);
    
    // 释放内存
    free(calories);
    
    return 0;
}


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int n, t, k;
    
    // 读取输入：n, t, k
    scanf("%d %d %d", &n, &t, &k);
    
    // 读取每个运动的卡路里
    int calories[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &calories[i]);
    }
    
    // 创建二维DP数组
    // dp[j][m] 表示选择j个运动，总卡路里为m的方案数
    int dp[k+1][t+1];
    
    // 初始化DP数组全部为0
    memset(dp, 0, sizeof(dp));
    
    // 初始化：选0个运动，卡路里为0的方案数为1
    dp[0][0] = 1;
    
    // 填充DP表格
    for (int i = 0; i < n; i++) {
        int cal = calories[i]; // 当前运动的卡路里
        
        // 需要从后往前遍历，避免重复计算
        for (int j = k; j >= 1; j--) {
            for (int m = t; m >= cal; m--) {
                dp[j][m] += dp[j-1][m-cal];
            }
        }
    }
    
    printf("%d\n", dp[k][t]);
    
    return 0;
}