购物单

可以将此问题转化为0-1规划问题。
得到最优解并输出最优方案的解法如下：

#coding=utf-8
'''
动态规划并输出路径
'''

while True:
    try:
        n, m = map(int,input().split())
        pri,annex = {},{}
        index = {} # 存储最优方案
        for i in range(0,n+1):
            index[i] = []
        for i in range(1,m+1):
            x,y,z = map(int,input().split())
            if z == 0:
                pri[i]=[x,y]
            else:
                if z in annex:
                    annex[z].append([i,x,y])
                else:
                    annex[z] = [[i,x,y]]
        dp = [0]*(n+1)
        for key in pri:
            money,value=[],[] # 金额和价值
            money.append(pri[key][0])
            value.append(pri[key][0]*pri[key][1])
            if key in annex:
                money.append(money[0]+annex[key][0][1])
                value.append(value[0] + annex[key][0][1]*annex[key][0][2])
                if len(annex[key])>1:
                    money.append(money[0] + annex[key][1][1])
                    value.append(value[0] + annex[key][1][1]*annex[key][1][2])
                    money.append(money[0] + annex[key][0][1] + annex[key][1][1])
                    value.append(value[0] + annex[key][0][1]*annex[key][0][2] + annex[key][1][1]*annex[key][1][2])
            for j in range(n,-1,-10):
                for k in range(len(money)): # 与0-1规划不同, 此处有len(money)种情况
                    if j - money[k]>=0:
#                         dp[j] = max(dp[j],dp[j-money[k]]+value[k]) # 动态规划关键步骤
                        if (dp[j-money[k]]+value[k]) > dp[j]:
                            dp[j] = dp[j-money[k]]+value[k]
                            if k == 0:
                                index[j] = index[j-money[k]] + [key]
                            elif k == 1:
                                index[j] = index[j-money[k]] + [key,annex[key][0][0]]
                            elif k == 2:
                                index[j] = index[j-money[k]] + [key,annex[key][1][0]]
                            elif k == 3:
                                index[j] = index[j-money[k]] + [key,annex[key][0][0],annex[key][1][0]]

        print(dp[n]) # 最优解
        print(index[n]) # 最优方案
    except:
        break