如何实现回溯打印背包中的物品（允许重复物品）？

Question

我有这个列表：

[['0', 'Cool Blue Marella Jug', '33', '15'],
 ['1', 'Weight Loss Pack', '55', '16'],
 ['2', 'Natural Black Vogue Lashes', '10', '6'],
 ['3', 'Paris Age Perfect Intense Nutrition Serum', '45', '22']​
  ...]

• 第一个数字是产品id
• 第二个数字（55，10，…）是价格和
• 第三个数字（16，6…）是利润。在

使用我下面的代码，如果我输入一个价格限制，我应该得到最高的利润的最佳组合项目（项目可以出售多次）。在

这是我的代码：

^{pr2}$

现在我需要修改它，以便它还返回一个列表chosenProduct，表示要销售的选定产品ID。在

例如，如果选择了两次产品冷蓝色marella水壶，选择了一次减肥包装，则chosenProduct=[0,0,1]

每当我找到一个新的最优值时，我试着将所选的产品存储在一个列表中，但是它存储了从值1到价格限制的所有最优值。我希望它只存储最新的产品选择和使用回溯从那里列出所有产品选择，构成利润。我该怎么做？在

Answer 1

def dp_pricelimit(product_list, price_limit):
    #to store results
    chosenProduct=[None]*(price_limit+1)
    memo=[0]*(price_limit+1)
    memo[0]=0
    for price in range(1, price_limit+1):
        for item in product_list:#go through the items
            if item[2]<=price:
                balance=price-item[2]

                profit=item[3] + memo[balance]
                if profit>memo[price]:#if found new optimal
                    memo[price]=profit
                    chosenProduct[price]=item[0]

    #use list to store list of item
    items = []
    #set i, the current price, to max price
    i = price_limit

    #while i is not a negative price
    while i >= 0:
        if chosenProduct[i] == None:
            break
        #append the item that was last added to make the optimal profit at price i.
        items.append(chosenProduct[i])
        #then jump back to before we added this item by decrementing the i, the current price, by the price of the last item that was added.
        i-=product_list[items[-1]][2]




    return memo[price_limit],items


print(dp_pricelimit([[0, 'Cool Blue Marella Jug', 33, 15],[1, 'Weight Loss Pack', 55, 16], [2, 'Natural Black Vogue Lashes', 10, 2], [3, 'Paris Age Perfect Intense Nutrition Serum', 45, 22]],88))

基本上，使用chosenproduct数组向后迭代。最后一项是为了创造最佳价值而增加的；它的成本可以减去，以在添加之前的价格获得最佳价值。然后在下一个价格下，我们将添加最后一个项目，以在chosenproduct数组中获得当前价格。祝你好运；）