代码之家 › 专栏 › 技术社区 › Sook Lim

如何实现回溯打印背包中携带的物品(允许重复物品)?

knapsack-problem backtracking dynamic-programming python

Sook Lim · 技术社区 · 6 年前

我有一份清单:

[['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…)是利润。

这是我的代码:

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

现在我需要修改它以便它也返回一个列表, chosenProduct ,表示要销售的选定产品标识。

例如。 如果产品酷蓝玛拉壶被选择了两次,减肥包被选择了一次,那么chosenProduct=[0,0,1]

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

1 回复 | 直到 6 年前

I. Cantrell 6 年前

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