代表团坐车 - 华为OD机试题

输入：
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]即为坐满汽车的方案数量。