题解 | #购物单#

def com_qikuang(N,price,inpot,my_fujian):
    r = []
    for i in range(N):
        if my_fujian[i] == []:
            r.append([[price[i], price[i]*inpot[i]]])
        elif my_fujian[i] == False:
            continue
        else:
            r.append([[price[i], price[i]*inpot[i]]])
            if len(my_fujian[i]) == 1:
                indx = my_fujian[i][0]
                r[-1].append([price[i]+price[indx],\
                          price[i]*inpot[i]+price[indx]*inpot[indx]])
            elif len(my_fujian[i]) == 2:
                indx1,indx2 = my_fujian[i][0],my_fujian[i][1]
                r[-1].append([price[i]+price[indx1],\
                          price[i]*inpot[i]+price[indx1]*inpot[indx1]])
                r[-1].append([price[i]+price[indx2],\
                          price[i]*inpot[i]+price[indx2]*inpot[indx2]])
                r[-1].append([price[i]+price[indx1]+price[indx2],\
                          price[i]*inpot[i]+price[indx1]*inpot[indx1]+price[indx2]*inpot[indx2]])
    return r

s = list(map(int,input().strip().split()))
mymoney,N = s[0]//10,s[1]
my_fujian = [[] for i in range(N)]
price = [0]*N
inpot = [0]*N
for i in range(N):
    s = list(map(int,input().strip().split()))
    price[i] = s[0]//10
    inpot[i] = s[1]
    if s[2] == 0:
        pass
    else:
        my_fujian[s[2]-1].append(i)
        my_fujian[i] = False
qingkuang = com_qikuang(N,price,inpot,my_fujian)
#print(qingkuang)
N = len(qingkuang)
# dp[剩下前多少个][剩下多少钱] 的最大效益
dp = [[0]*(mymoney+1) for i in range(N)]
for j in range(mymoney+1):
    for i in range(N):
    # 情况 i 对应的钱
        if i == 0:
            ziqingkuang = qingkuang[i]
            for qing in ziqingkuang:
                if j >= qing[0]:
                    dp[i][j] = max(qing[1],dp[i][j])
                else: # 容不下现在的，但是也不是就0了啊！！！
                    dp[i][j] = max(dp[i-1][j],dp[i][j])
        else:
            ziqingkuang = qingkuang[i]
            for qing in ziqingkuang:
                if j >= qing[0]:
                    dp[i][j] = max((dp[i][j], dp[i-1][j], dp[i-1][j-qing[0]]+qing[1]))
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j])
print(dp[len(dp)-1][len(dp[0])-1]*10)