动态规划类的问题

就是，新手，真的挺难的，我看了一个晚上QAQ

最最重要的是，想清楚这个过程。想清楚了，交给代码去“动态规划”。

害，说了好像没说，一点点进步吧，朋友~

money, capacity = map(int, input().split(" "))

# money 都是 10 的整数，整除后可以减小循环次数
money //= 10

# (capacity+1,3) 矩阵
weight       = [[0]*3 for _ in range(capacity+1)]

# (capacity+1,3) 矩阵
satisfaction = [[0]*3 for _ in range(capacity+1)]

# (capacity+1,money+1) 矩阵
answer       = [[0]*(money+1) for _ in range(capacity+1)]

for i in range(1, capacity+1):
    
    # 把商品的 `价钱`,`重要度`,`是否为主件` 取出来
    price, importance, primary = map(int,input().split(" "))
    
    # 前面 money 除以十了，所以这里也要除以十
    price //= 10

    # 如果是主件
    if primary == 0:
        weight[i][0] = price
        satisfaction[i][0] = price * importance
        
    # 如果不是主件,就要找到主件指向的商品
    # 但是又因为,题目说一个 `主件` 可以有 `两个附件`
    # 所以还不能写 `else`
    # 得在确定了它有 多少个附件 之后才能
    elif weight[primary][1] == 0:
        weight[primary][1] = price
        satisfaction[primary][1] = price * importance

    # 如果还遇到一个 `附件`,这下就是 `第二个附件` 了,也是最后一个
    else:
        weight[primary][2] = price
        satisfaction[primary][2] = price * importance

# 好了,现在就把 weight 和 satisfaction 搞定了
# 现在可以开始遍历了

# print(weight)
# print(satisfaction)
# print(answer)

# 从商品的种类开始遍历
for i in range(1, capacity+1):
    
    # 从现在的 money（除以十了的）开始遍历到 0 
    for j in range(money,-1,-1):

        # 如果当前的钱 能 支付起当前主件
        if j >= weight[i][0]:

            # 那么，不买的话，有多少价值；买的话，又会有多少价值
            answer[i][j] = max(answer[i-1][j], answer[i-1][j-weight[i][0]]+satisfaction[i][0])

            # 如果当前的钱 还能买得起 当前主件+附件1
            if j>=(weight[i][0]+weight[i][1]):
                answer[i][j] = max(answer[i][j], answer[i-1][j], answer[i-1][j-weight[i][0]-weight[i][1]]+satisfaction[i][0]+satisfaction[i][1])

            # 如果当前的钱 还能买得起 当前主件+附件2
            if j>=(weight[i][0]+weight[i][2]):
                answer[i][j] = max(answer[i][j], answer[i-1][j], answer[i-1][j-weight[i][0]-weight[i][2]]+satisfaction[i][0]+satisfaction[i][2])
                
                # 如果当前的钱 还能买得起 当前主件+附件1+附件2
                if j>=(weight[i][0]+weight[i][1]+weight[i][2]):
                    answer[i][j] = max(answer[i][j], answer[i-1][j], answer[i-1][j-weight[i][0]-weight[i][1]-weight[i][2]]+satisfaction[i][0]+satisfaction[i][1]+satisfaction[i][2])

        # 如果买不起了，就不买了呗，满意度就跟上一行一样
        else:
            answer[i][j] = answer[i-1][j]

print(answer[-1][-1]*10)