#P3201. 会议接待(200分)
-
1000ms
Tried: 118
Accepted: 34
Difficulty: 6
所属公司 :
华为od
会议接待(200分)
题面描述
某组织举行会议,来了多个代表团同时到达,接待处只有一辆汽车,可以同时接待多个代表团。为了提高车辆利用率,请帮接待员计算可以坐满车的接待方案,输出方案数量。
思路
这是一个典型的子集和问题,需要找到所有代表团的子集,使得这些代表团的人数之和恰好等于汽车的容量。由于代表团可能有相同的人数,但它们是不同的代表团,因此需要考虑每个代表团的唯一性。
使用动态规划(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]