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

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']
  ...]

第一个数字是产品编号，
第二个数字 (55,10,...) 是价格
第三个数字(16,6...)是利润。

使用我下面的代码，如果我输入一个价格限制，我应该通过最好的物品组合获得最高利润（物品可以多次出售）。

这是我的代码：

def dp_pricelimit(product_list, price_limit):
    #to store results
    chosenProduct=[0]*(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]

    return memo[price_limit],chosenProduct

现在我需要修改它，以便它也 returns 一个列表，chosenProduct，代表所选的要出售的产品 ID。

例如如果产品cool blue marella jug被选择了两次并且减肥包被选择了一次列表应该是，chosenProduct=[0,0,1]

每当我发现一个新的最优值时，我都尝试将选择的产品存储在列表中，但它存储了它找到的从值 1 到 price_limit 的每个最优值。我希望它只存储选择的最新产品，并从那里使用回溯来列出所有选择的构成利润的产品。我该怎么做？

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 数组中获得当前价格。祝你好运 ;)

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

How to implement backtracking to print the items taken in knapsack(repetition of items allowed)?

python

knapsack-problem

dynamic-programming

backtracking