题目描述

题目

有一个箱子容量为 V（正整数，0≤V≤20000），同时有n个物品（0 \leq n \leq 30$），每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述

输入第一行，一个整数，表示箱子容量。

第二行，一个整数 n，表示有 nn 个物品。

接下来 n 行，分别表示这 n 个物品的各自体积。

输出描述

输出一行，表示箱子剩余空间。

输入输出样例

示例 1

输入

1. 24
2. 6
3. 8
4. 3
5. 12
6. 7
7. 9
8. 7

输出

0

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路

这道题是背包问题的简化版，即不需要管每个物品的价值。我们只需要从这些货物中选出和最接近箱子容量的组合即可。

我们设dp[j]为箱子容积为时，所有货物中选出所得的物品的最接近v的体积。

设计动态转移方程：我们遍历每一个货物i，让箱子体积j从v减小到i的体积，我们有两种选法，一是不拿这个货物，不做任何操作，dp[i][j]等于之间的值dp[i-1][j]；另外一种拿这个货物是找到dp[i-1][j-h[i]]即当前的最优解减去h[i]的最优解，dp[i-1][j-h[i]]+h[i]就是我们当前的最优解

状态转移方程如下：

dp[j]=max(dp[j],dp[j-h[i]]+h[i])

代码

1. v = int(input())
2. n = int(input())
3. h = []
4. dp=[0]*10000
5. for i in range(n):
6.     h.append(int(input()))
7. for i in range(n):
8. for j in range(v,h[i]-1,-1):
9.         dp[j]=max(dp[j],dp[j-h[i]]+h[i])
10. print(v-dp[v])