题面描述

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团。为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。

思路

这是一个典型的子集和问题，需要找到所有代表团的子集，使得这些代表团的人数之和恰好等于汽车的容量。由于代表团可能有相同的人数，但它们是不同的代表团，因此需要考虑每个代表团的唯一性。

使用动态规划（DP）来解决这个问题。定义 dp[i][j] 为前 i 个代表团中，选取一些代表团使得人数之和为 j 的方案数。状态转移方程为：

• 如果不选第 i 个代表团：dp[i][j] += dp[i-1][j]
• 如果选第 i 个代表团且 j >= group[i-1]：dp[i][j] += dp[i-1][j - group[i-1]]

初始化条件：

• dp[0][0] = 1，表示不选任何代表团时人数和为 0 的方案数为 1。
• 其他 dp[0][j] = 0（j > 0），表示不选任何代表团时人数和不为 0 的方案数为 0。

最终答案为 dp[n][capacity]，其中 n 是代表团的数量，capacity 是汽车的载客量。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 读取代表团人数的输入
    string line;
    getline(cin, line);
    vector<int> groups;
    string num = "";
    for(char c : line){
        if(c == ','){
            if(!num.empty()){
                groups.push_back(stoi(num));
                num = "";
            }
        }
        else{
            num += c;
        }
    }
    if(!num.empty()) groups.push_back(stoi(num));

    // 读取汽车容量
    int capacity;
    cin >> capacity;

    int n = groups.size();
    // dp[i][j]表示前i个代表团中，选取一些代表团使得人数和为j的方案数
    vector<vector<int>> dp(n+1, vector<int>(capacity+1, 0));
    dp[0][0] = 1; // 初始化

    for(int i=1; i<=n; ++i){
        for(int j=0; j<=capacity; ++j){
            // 不选第i个代表团
            dp[i][j] = dp[i-1][j];
            // 选第i个代表团
            if(j >= groups[i-1]){
                dp[i][j] += dp[i-1][j - groups[i-1]];
            }
        }
    }

    // 输出结果
    cout << dp[n][capacity] << endl;

    return 0;
}

python

# 读取代表团人数的输入
import sys

line = sys.stdin.readline().strip()
groups = list(map(int, line.split(',')))

# 读取汽车容量
capacity = int(sys.stdin.readline())

n = len(groups)
# dp[j]表示人数和为j的方案数
dp = [0] * (capacity + 1)
dp[0] = 1  # 初始化

for group in groups:
    # 从后往前更新，避免重复使用同一个代表团
    for j in range(capacity, group -1, -1):
        dp[j] += dp[j - group]

# 输出结果
print(dp[capacity])

java

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取代表团人数的输入
        String line = sc.nextLine().trim();
        String[] parts = line.split(",");
        int[] groups = new int[parts.length];
        for(int i=0;i<parts.length;i++) {
            groups[i] = Integer.parseInt(parts[i]);
        }
        // 读取汽车容量
        int capacity = sc.nextInt();
        int n = groups.length;
        // dp[i][j]表示前i个代表团中，选取一些代表团使得人数和为j的方案数
        int[][] dp = new int[n+1][capacity+1];
        dp[0][0] = 1; // 初始化
        for(int i=1;i<=n;i++){
            for(int j=0;j<=capacity;j++){
                // 不选第i个代表团
                dp[i][j] = dp[i-1][j];
                // 选第i个代表团
                if(j >= groups[i-1]){
                    dp[i][j] += dp[i-1][j - groups[i-1]];
                }
            }
        }
        // 输出结果
        System.out.println(dp[n][capacity]);
    }
}

题目描述

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团，为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。

约束:

一个团只能上一辆车，并且代表团人数 (代表团数量小于 $30$ ，每个代表团人数小于 $30$ )小于汽车容量(汽车容量小于 $100$ )

需要将车辆坐满

输入描述

第一行 代表团人数，英文逗号隔开，代表团数量小于 $30$ ，每个代表团人数小于 $30$

第二行 汽车载客量，汽车容量小于 $100$

输出描述

坐满汽车的方案数量，如果无解输出 $0$

样例1

输入

5,4,2,3,2,4,9
10

输出

4

说明

解释 以下几种方式都可以坐满车，所以，优先接待输出为 $4$

$[2,3,5]$

$[2,4,4]$

$[2,3,5]$

$[2,4,4]$