题解 | #[NOIP2001]装箱问题#

import sys

'''
接收箱子的体积和物品，并将物品的体积保存到列表中
'''
Vs = int(input())
n = int(input())

i=1
V=[]
while i<=n:
    V.append(int(input())
    )
    i+=1
#创建一个dp数组，保存在箱子体积为j时的到物品i为止最大的体积

dp=[[0 for j in range(Vs+1)] for i in range(len(V))]

for i in range(Vs+1):
    if V[0]<=i:
        dp[0][i]=V[0]

#如果i的体积比箱子的体积j大，不能装入，
for i in range(1,len(V)):
    for j in range(Vs+1):
        if V[i]>j:
            dp[i][j]=dp[i-1][j]
#如果i的体积比j的体积小，要比较装入i的体积和不装入i的体积哪个大
        else:
            dp[i][j]= max(dp[i-1][j],dp[i-1][j-V[i]]+V[i])
#for x in range(len(dp)):
#    print(dp[x])
print(Vs-max(map(max,dp)))