题解 | [NOIP2001]装箱问题 Python3
[NOIP2001]装箱问题
https://www.nowcoder.com/practice/55100a6608ad4656849dbd1f16d044cb
import sys
# 0-1 背包问题，动态规划解决
# 总共n个物品，V的容量
# 对于每个物品，在考虑最大容量的结果的时候，只有它被装进去，或者没有被装进去这两种情况
# 首先明确一点，对于n个物品V的容量的最后的解决方案，是可以由n2个物品V2的容量推导而来，n2<n, V2<V
# dp[i][j] 表示当考虑第i个物品的时候，最大容量为j的时候最大的体积
# dp[i][j] = max(dp[i-1][j-v]+v, dp[i-1][j]) # dp[i-1[j-v]表示把物品i放进背包的情况
V = int(input())
n = int(input())
weights = []
for _ in range(n):
weights.append(int(input()))
dp = [[0]*(V+1) for _ in range(n+1)]
# 因为考虑到i-1, 所以范围从0~n+1
for i in range(1,n+1):
for j in range(1,V+1):
if j < weights[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j-weights[i-1]]+weights[i-1], dp[i-1][j])
print(V-dp[-1][-1])
