题解 | #装箱问题#

01背包特殊情况

import sys

def solution(V,n,v):
    dp = [0 for _ in range(V+1)]
    dp[0] = 1
    for i in range(n):
        for j in range(V,v[i]-1,-1):#01背包之刚好装满
            if dp[j-v[i]] >0:
                dp[j] = 1 
    #print(dp)
    for j in range(V,-1,-1):
        if dp[j]:
            return V-j
if __name__ == "__main__":
    V = int(input())
    n = int(input())
    v = [0 for _ in range(n)]
    for i in range(n):
        v[i] = int(input())
    res = solution(V,n,v)
    print(res)