题解 | 购物单

from enum import IntEnum
import sys
input = sys.stdin.readline

def main():
    # 读取总预算 n 和物品总数 m
    n, m = map(int, input().split())
    n //= 10  # 所有物品的价格都是10的倍数，所以可以除以 10 缩小空间

    # 由于附件和主件的顺序不定，所以先将所有物品的信息保存下来
    V = [0] * (m+1)
    VAL = [0] * (m+1)
    Q = [0] * (m+1)
    for i in range(1,m+1):
        v, w, q = map(int, input().split())
        v //= 10  # 将价格缩小，方便计算
        V[i] = v
        VAL[i] = v * w
        Q[i] = q

    # 主件作为单位，附件作为主件的属性/元素
    ### 主件items[i] = [v, val, [附件1, 附件2]]——v代表价格，val代表满意度
    items = {}
    #（1） 第一次遍历，初始化主件信息
    for i in range(1,m+1):
        if Q[i] == 0:
            items[i] = [V[i], VAL[i], []]
    #（2）第二次遍历，初始化附件信息
    for i in range(1,m+1):
        if Q[i] != 0:
            items[Q[i]][2].append((V[i], VAL[i]))

    
    # 动态规划算法解题：0/1背包问题
    dp = [0] * (n+1) # dp[j]表示预算为j时的最大满意度值
    for v_main, val_main, atts in items.values():
        for j in range(n,-1,-1):  
        # 从后向前遍历，保证每次更新都是在上一次外循环的基础上
            # 1、只买主件
            if j >= v_main:
                dp[j] = max(dp[j], dp[j-v_main] + val_main)
            # 2、买主件 + 附件1
            if len(atts) >= 1:
                v1, val1 = atts[0]
                if j >= v_main + v1:
                    dp[j] = max(dp[j], dp[j-v_main-v1] + val_main + val1)
            # 3、买主件 + 附件2  / 买主件 + 两个附件
            if len(atts) >= 2:
                v1, val1 = atts[0]
                v2, val2 = atts[1]
                if j >= v_main + v2:
                    dp[j] = max(dp[j], dp[j-v_main-v2] + val_main + val2)
                if j >= v_main + v1 + v2:
                    dp[j] = max(dp[j], dp[j-v_main-v1-v2] + val_main + val1 +val2)
    # 输出最大满意度
    print(dp[n]*10)

if __name__ == '__main__':
    main()

• 由于每个物品的价格都是10的倍数，所以将预算与价格都整除10，简化计算，避免算力浪费
• 首先使用列表V, VAL, Q将所有物品的信息都保存下来
• 将主件作为算法检索的单位，将附件作为主件的一种属性（附件数<=2，那么在检索时所耗费的时间就是有限的）
• DP动态规划算法解决0/1背包问题：将预算的增加作为大循环/外循环，将主件物品的循环作为内循环/小循环，判断要不要当前物品。注意对于每一个主件物品，还需要判断要不要附件物品（也就是当前主件物品与附件物品的组合）
• 为了节省空间，原本两重循环需要一个二维数组保存每次的结果，现在改为一维数组dp[]，为了保证结果正确，那么内循环/小循环从后向前遍历（因为循环内的操作只用到了数组dp当前元素i之前的元素值，所以可以改其后的元素值，不能改之前的）