分支定界背包算法的问题

Question

我正在做一个用 Python 编写的背包优化练习。目标是用具有一定价值和重量的物品填充重量有限的背包，从而使背包的总价值最大化。当找到更好的解决方案时，我运行遇到了设置变量的问题。

我创建了一个没有任何限制的简化版本的代码，展示了我的问题。由于没有约束，第一个解决方案始终是最佳解决方案，因为这是采用所有项目的解决方案。

代码中有一个 if 语句，用于设置 max_value 和 best_taken 变量，以防找到更好的解决方案。

但是：当代码末尾的 print 语句打印 max_value 和 best_taken 变量时，max_value 显示正确的值（第一个索引的总和分配给 items 变量的列表列表）。 best_taken 值始终以 [0,0] 结束，其中预期值为 [1,1]（=同时取两项）。

我做错了什么？

items = [[5,3],[4,1]]
depth = 0


class BranchBound():
    def __init__(self):
        self.max_value = 0
        self.best_taken = []
        self.local_value = 0
        self.local_taken = [0] * len(items)
       
    
    def branch_and_bound(self,depth):
        new_depth = depth
        if new_depth < len(items):
            #Take item
            self.local_taken[new_depth] = 1           
            new_depth += 1
            self.branch_and_bound(new_depth)
            
            # Do not take item
            new_depth = depth
            self.local_taken[new_depth] = 0
            new_depth += 1
            self.branch_and_bound(new_depth)
        else:
            self.local_value = 0
            for i,j in zip(self.local_taken,items):
                self.local_value += i*j[0]
            if self.local_value > self.max_value:
                print("ping")
                self.max_value = self.local_value
                self.best_taken = self.local_taken
            
        
bb = BranchBound()
bb.branch_and_bound(depth)
print(bb.max_value)
print(bb.best_taken)

Answer 1

您需要复制local_taken。将数组分配给属性只是添加对相同（可变）数组的引用

self.best_taken = self.local_taken[:]

分支定界背包算法的问题

Problems with a branch and bound knapsack algorithm

python

optimization

class

knapsack-problem