有什么办法可以使我在背包问题上的代码更好?

我正在研究背包问题(请选择一组价格最高且总重量最多为W的物品)

但!不允许同时选择两个连续项目(项目i和项目i + 1)或同一项目。

就目前而言,我的做法很简单

prices    = [1,6,3,3,4,3,7]
weights = [1,3,2,1,2,2,2]
weight_set = 3

max_1 = 0;max_2 = 0
price_max = 0
for idx,_ in enumerate(prices):
    for i,_ in enumerate(prices):
        if i != idx and i != idx+1 and i != idx-1 : #Not the same and not consecutive items
            if weights[idx]+weights[i] <= weight_set and prices[idx]+prices[i] > price_max: # weight should equal to weight_set 
                max_1 = idx; max_2 = i # for first item and second item
                price_max = prices[idx]+prices[i]

答案是正确的

price[max_1]=>3 and price[max_2]=>7 << weight equal to weight_set and price is maximum and not consecutive items

我的问题是我应该怎么做才能使这个算法更好?改变算法?还是使用动态编程? (以缩短计算时间或处理最坏的情况)

谢谢你的回答。

评论