题解 | #购物单#

01背包问题中的一种，属于有依赖的背包问题，解决方法是先把有依赖的物品的各种组合列出来作为一组，再当作分组的背包问题去解决。

首先是01背包，本题使用代码解决的基本思路：

使用二维数组的两个下标代表物品序号和背包容量（钱数），数组内的值代表价值（满意度）。

当数组的行号增加1时，表示可供选择的物品增加1。当列号增加1时，表示可供使用的背包容量增加1。

第一行因为可选物品序号为0，所以价值全为0。

同理，第一列因为背包容量为0，所以价值也全为0。

在当前的可选物品前提下，同一行需确保在每次容量增加时都能选择到的物品价值最大。

在当前的背包容量下，同一列需要确保在每次增加可选物品时能选择到的物品价值最大。

满足上面两个条件后，数组的最后一行中的最后一个数即最优解。

t = 5 #假设有5件物品
c = 10 #容量（钱数）为10
i=[[8,6],[10,4],[4,2],[5,4],[5,3]] # 物品信息 [价值, 体积]
dp = [[0 for _ in range(c+1)]]
print(dp)
for n in range(1,t+1): # 行号（物品序号）逐渐递增，t+1代表递增至题目要求的物品序号
    tl = [0 for _ in range(c+1)]
    for v in range(c+1):# 列号（容量）逐渐递增，c+1代表递增至题目要求的容量
        if v >= i[n-1][1]: # 背包容量大于当前物品的体积时才有可能选择该物品，物品的下标为n-1
            # 假设n=1，n-1即上一行，dp[0]这一行全为0，所以只要背包装得下序号为1的物品（v>=6）,其价值都为8
            # print(dp[n - 1][v], dp[n - 1][v - i[n-1][1]])
            tl[v] = max(dp[n - 1][v], dp[n - 1][v - i[n-1][1]] + i[n-1][0])
                        # dp[n - 1][v]截至上一物品能选择到的最大价值             # v - i[n-1][1] 意思是减去当前物品所需的容量后剩余的容量，dp[n - 1][v - i[n-1][1]] + i[n-1][0] 意思是剩余容量能装物品的价值加上当前物品的价值
    dp.append(tl)
print(dp[t][-1])

回到本题，物品最多有两个附件，且如果选择附件必须选择主件，那么主附件可以当成是几种组合，1.主，2.主+附1，3.主+附2，4.主+附1+附2

把这几种组合当成是一组，在选择到有附件的物品时，则再从这一组中选择使得价值最大的组合。

同时，因为取最大值只需要用到第n行和n-1行，所以可以优化为两个数组，而由于取最大值只需要改变v大于物品的体积的一项，可以通过下标递减优化为一个数组。

data = list(map(int, input().split(' ')))
l = [[] for _ in range(data[1])]
for i in range(data[1]):
    t = list(map(int, input().split(' ')))
    l[i] = t + l[i]
    if t[2] != 0:  # 属于附件则把下标存储在主件的信息组里
        l[t[2] - 1].append(i)
tl = [0 for _ in range(int(data[0] / 10) + 1)]  # 钱数是10的倍数
for n in range(data[1]):
    if l[n][2] == 0:  # 是主件则参与比较
        m = int(data[0] / 10)  # 最大钱数
        msum = l[n][0] * l[n][1]  # 当前物品满意度
        if len(l[n]) == 4:  # 有一件附件
            anum = l[n][3]  # 附件序号
            asum = l[anum][0] * l[anum][1]  # 附件满意度
            while True:
                tl[m] = max(tl[m], tl[m - int(l[n][0] / 10)] + msum)
                if m >= (l[n][0] + l[l[n][3]][0]) / 10:  # 钱数大于主件+附件价格则进行比较
                    tl[m] = max(tl[m], tl[m - int((l[n][0] + l[anum][0]) / 10)] + msum + asum)
                    pass
                m -= 1
                if m < l[n][0] / 10:  # 钱数少于主件价格则退出比较
                    break
        elif len(l[n]) == 5:  # 有两件附件
            anum1 = l[n][3]
            anum2 = l[n][4]
            asum1 = l[anum1][0] * l[anum1][1]
            asum2 = l[anum2][0] * l[anum2][1]
            while True:
                tl[m] = max(tl[m], tl[m - int(l[n][0] / 10)] + msum)
                if m >= (l[n][0] + l[anum1][0]) / 10:
                    tl[m] = max(tl[m], tl[m - int((l[n][0] + l[anum1][0]) / 10)] + msum + asum1)
                if m >= (l[n][0] + l[anum2][0]) / 10:
                    tl[m] = max(tl[m], tl[m - int((l[n][0] + l[anum2][0]) / 10)] + msum + asum2)
                if m >= (l[n][0] + l[anum1][0] + l[anum2][0]) / 10:  # 钱数大于主件+两个附件价格则进行比较
                    tl[m] = max(tl[m],
                                tl[m - int((l[n][0] + l[anum1][0] + l[anum2][0]) / 10)] + msum + asum1 + asum2)
                m -= 1
                if m < l[n][0] / 10:
                    break
        else:
            while True:
                tl[m] = max(tl[m], tl[m - int(l[n][0] / 10)] + msum)
                m -= 1
                if m < l[n][0] / 10:
                    break
print(tl[-1])