华为od机试真题 — 代表团坐车(Python)

题目描述

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

约束：

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

输入描述

第一行 代表团人数，英文逗号隔开，代表团数量小于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]

题解

为了找到所有可能的方案使车辆正好装满，我们可以使用动态规划的方法：

1. 定义状态： 定义一个一维数组dp，其中dp[cap]表示容纳cap人的方案数。
2. 初始状态： 将dp[0]设为1，因为不带走任何代表团也是一种方案。
3. 状态转移： 对于每一个代表团人数x，遍历数组dp，更新dp[cap]。具体的更新方式是：

• 对于每一个cap，如果cap >= x，则更新dp[cap] += dp[cap - x]。

4. 结果： 最终，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])

相关练习题

2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏