HJ16-购物单

这是一道典型的0-1背包问题，一开始的反应就是外层循环正向遍历物品，内层循环反向遍历背包容量。但由于物品增加了附件这一属性，使得这道题难度增加了不少，可以参考该视频处理物品的思路，每个物品用长度为6的数组来分别保存索引为i的物品主件价格，主件价值，附件1价格，附件1价值，附件2价格，附加2价值。对物品的处理弄明白了，其他地方跟之前做过的0-1背包问题都差不多了。

# python
money, n = map(int, input().split(" "))
# dp[j] 表示money为j的背包买各种物品所能得到的最大价值
money //= 10    # 已知money为10的倍数，将输入的背包容量除以10，使得内层遍历次数大大减少
items = [[0] * 6 for _ in range(n)]    # 存放每个物品的信息
dp = [0] * (money + 1)
for i in range(n):
    price, weight, parent = map(int, input().split(" "))
    if parent:    # 如果parent不为0，属于附件
        if items[parent - 1][2] == 0:    # 还没有附件1
            items[parent - 1][2] = price // 10
            items[parent - 1][3] = price * weight
        else:                            # 已有附件1，加到附件2
            items[parent - 1][4] = price // 10
            items[parent - 1][5] = price * weight
    else:         # 没有parent，为主件
        items[i][0] = price // 10
        items[i][1] = price * weight
for i in range(n):    # 外层遍历每个物品
    if items[i][0] == 0:    # 附件空出来的索引，直接跳过
        continue
    price = items[i][0]
    value = items[i][1]
    price1 = items[i][2]
    value1 = items[i][3]
    price2 = items[i][4]
    value2 = items[i][5]
    for j in range(money, price - 1, -1):    # 主要money还能购买，计算四种情况得到的最大价值
        if j >= price:
            dp[j] = max(dp[j], dp[j - price] + value)
        if j >= price + price1:
            dp[j] = max(dp[j], dp[j - price - price1] + value + value1)
        if j >= price + price2:
            dp[j] = max(dp[j], dp[j - price - price2] + value + value2)
        if j >= price + price1 + price2:
            dp[j] = max(dp[j], dp[j - price - price1 - price2] + value + value1 + value2)
print(dp[-1])