题解 | #购物单#

python3
本质上是一个带额外约束的背包问题，可以用动态规划的思路求解。
首先，可以先进行的处理是

1.将每个物品的价格与重要度相乘，作为价值向量v
2.计算购买某个物品时，需要额外花的钱ex_w，和额外产生的价值ex_v
3.将每个物品的价格和购买该物品时需要额外话的钱相加作为该物品的w的值，该物品产生的价值v和额外产生的价值ex_v相加作为该物品的v
之后，就可以按求解0-1问题的基本步骤去做了

建立矩阵dp，矩阵有5行（一共5个物品），有1000+1列（一共1000元）
先填第一行，如果钱j(背包容量)小于产生的价值v[i]（物品的价值），那么填0，否则，填v[i]
再填其余行
如果j小于v[i],填dp[i-1,j],
如果j大于等于v[i],填max( dp[i-1,j] ,dp[i-1,j-w[i]]+v[i])

n, m = map(int,input().split())
primary, annex = {}, {}
for i in range(1,m+1):
    x, y, z = map(int, input().split())
    if z==0:
        primary[i] = [x, y]
    else:
        if z in annex:
            annex[z].append([x, y])
        else:
            annex[z] = [[x,y]]
dp = [0]*(n+1)
for key in primary:
    w, v= [], []
    w.append(primary[key][0])#1、主件
    v.append(primary[key][0]*primary[key][1])
    if key in annex:#存在附件
        w.append(w[0]+annex[key][0][0])#2、主件+附件1
        v.append(v[0]+annex[key][0][0]*annex[key][0][1])
        if len(annex[key])>1:#附件个数为2
            w.append(w[0]+annex[key][1][0])#3、主件+附件2
            v.append(v[0]+annex[key][1][0]*annex[key][1][1])
            w.append(w[0]+annex[key][0][0]+annex[key][1][0])#4、主件+附件1+附件2
            v.append(v[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
    for j in range(n,-1,-10):#物品的价格是10的整数倍
        for k in range(len(w)):
            if j-w[k]>=0:
                dp[j] = max(dp[j], dp[j-w[k]]+v[k])    
print(dp[n])