题解 | 点菜问题

import sys
def dp(num,total,weight,value):
    #dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i-1]+value[i-1]])
    dp=[0]*(total+1)
    for i in range(1,num+1):
        for j in range(total,0,-1):
            if j-weight[i-1]>=0:
                dp[j]=max(dp[j],dp[j-weight[i-1]]+value[i-1])
    print(dp[-1])
if __name__=='__main__':
    it=iter(sys.stdin)
    while 1:
        try:
            total,num=map(int,next(it).strip().split())
            weight=[]
            value=[]
            for _ in range(num):
                a,b=map(int,next(it).strip().split())
                weight.append(a)
                value.append(b)
            dp(num,total,weight,value)
        except:
            break

经典的01背包最大价值问题，进行压缩数组优化，时间n^2，空间n