题解 | [NOIP2001]装箱问题 Python3

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])