题解 | 装箱问题

V=int(input())
n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

# dp[j] 表示是否存在一个子集，使得体积和正好等于 s
dp=[False]*(V+1)
dp[0]=True
for w in a:#每考虑一个物体，dp[j]都会被更新
    if w>V:
        continue
    for j in range(V,w-1,-1):#对于j<=w的dp[j]肯定不需要更新
        if dp[j-w]: #j是V,V-1,...,w 这样递减的，最后一步必然是j-w=0
            dp[j]=True

for k in range(V,-1,-1):
    if dp[k]:
        print(V-k)
        break

降低空间复杂度：改用一维 dp, 让dp[j] 表示是否存在一个子集，使得体积和正好等于 s