代表团坐车 - 华为OD统一考试

OD统一考试（B卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

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

约束：

一个团只能上一辆车，并且代表团人数(代表团数量小于30，每个代表团人数小于30)小于汽车容量(汽车容量小于100)。
需要将车辆坐满。

输入描述

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

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

输出描述

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

示例1

输入：
5,4,2,3,2,4,9
10

输出：
4

说明：
以下几种方式都可以坐满车，[2,3,5]、[2,4,4]、[2,3,5]、[2,4,4]

题解

这个问题是经典的01背包问题可以使用动态规划来解决。

定义一个一维数组dp，其中dp[cap]表示容纳cap人的方案数。

初始时，将dp[0]设为1，因为不带走任何代表团也是一种方案。

然后，对于每一个代表团人数 x，遍历数组dp，更新dp[cap]。具体的更新方式是，对于每一个 cap，如果 cap >= x，则更新dp[cap] += dp[cap - x]。这表示当前容量为cap的方案数等于之前容量为cap - x的方案数加上带上当前代表团的方案数。

最终，dp[capacity]即为坐满汽车的方案数量。

Java

import java.util.Arrays;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取代表团人数
        String[] groupsStr = scanner.nextLine().split(",");
        int[] groups = Arrays.stream(groupsStr).mapToInt(Integer::parseInt).toArray();

        // 读取汽车载客量
        int capacity = scanner.nextInt();

        // dp[cap] 表示容纳 cap 人的方案数
        int[] dp = new int[capacity + 1];
        dp[0] = 1;

        for (int x : groups) {
            for (int cap = capacity; cap >= x; cap--) {
                dp[cap] += dp[cap - x];
            }
        }

        System.out.println(dp[capacity]);
    }
}

Python

groups = list(map(int, input().split(",")))
capacity = int(input())

# dp[cap] 表示容纳 cap 人的方案数
dp = [0] * (capacity + 1)
dp[0] = 1

for x in groups:
    for cap in range(capacity, x - 1, -1):
        dp[cap] += dp[cap - x]

print(dp[capacity])

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	vector<int> groups;
	int t,capacity;
	while(cin >> t) {
		groups.push_back(t);
		if(cin.peek() == ',') {
			cin.ignore();
		} else {
			cin >> capacity;
			break;
		}
	}

	vector<int> dp(capacity + 1, 0);
	dp[0] = 1;

	for(int i = 0; i < groups.size(); i++) {
		int x = groups[i];
		for(int cap = capacity; cap >= x; cap--) {
			dp[cap] += dp[cap - x];
		}
	}

	cout << dp[capacity] << endl;

	return 0;
}