刷题笔记合集🔗

代表团坐车

问题描述

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

约束:

1. 一个团只能上一辆车，并且代表团人数（代表团数量小于 ，每个代表团人数小于 ）小于汽车容量（汽车容量小于 ）
2. 需要将车辆坐满

输入格式

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

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

输出格式

坐满汽车的方案数量。

如果无解输出 。

样例输入

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

样例输出

4

数据范围

• 代表团数量
• 每个代表团人数
• 汽车容量

题解

这道题目实际上是经典的背包问题变种，具体来说，是"恰好装满背包"的01背包问题。

首先理解题目：我们有多个代表团，每个团有固定的人数，目标是选择若干个代表团，使得他们的总人数恰好等于汽车的载客量。需要计算的是有多少种不同的选择方案。

这类问题的关键在于定义状态和转移方程：

1. 状态定义：dp[i][j] 表示前i个代表团中，选择若干个使得总人数恰好为j的方案数
2. 转移方程：对于每个代表团，有两种选择：选或不选
   • 不选：dp[i][j] = dp[i-1][j]
   • 选：dp[i][j] += dp[i-1][j-num[i-1]]
   • 总方案数 = 选 + 不选

初始条件：dp[0][0] = 1，表示不选任何代表团，总人数为0的方案数为1种。

以样例为例：代表团人数[5,4,2,3,2,4,9]，汽车容量10

• 选择[2,3,5]刚好坐满车（人数总和为10）
• 选择[2,4,4]刚好坐满车（人数总和为10） 注意样例中提到有4种方案，这是因为有两个值为2的代表团和两个值为4的代表团，排列组合后得到4种不同方案。

实现上，我们可以使用二维数组，也可以使用一维滚动数组来优化空间。由于代表团数量和汽车容量都不大（都小于100），时间复杂度O(n*m)和空间复杂度O(m)在题目范围内都是可接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取代表团人数
teams = list(map(int, input().split(',')))
# 读取汽车容量
capacity = int(input())

# 使用01背包求解装满背包的方案数
def count_ways(nums, target):
    # dp[j] 表示总人数恰好为j的方案数
    dp = [0] * (target + 1)
    # 初始条件：总人数为0的方案数为1
    dp[0] = 1
    
    # 遍历每个代表团
    for num in nums:
        # 必须从大到小遍历，避免重复计算
        for