以正确的顺序选择列表中价值最高的项目

Question

我正在使用我现在正在研究的分支定界算法解决背包问题。在算法中，我想开始选择密度最高的项目（value/weight）。我创建了一个名为“密度”的列表并进行了必要的计算。我每次都需要从该列表中选择最大值。但每次我尝试时，顺序都会混合。我需要更新变量“a”，因为每次我删除一个项目时，列表都会变小。但是不知道怎么更新。我需要帮助以正确的顺序选择项目。

重量、价值、密度都是列表。 capacity 和 room 是问题中给出的整数值。这是密度列表。

我想要的是，得到这个列表中最大项的索引。然后，从“容量”中减去它的“重量”，以求出还有多少“空间”。并将“价值”加到“最高”上，以达到背包中可以添加的最高价值。在我对第一个项目执行此操作后，然后迭代它直到没有或只剩下很少的空间。

    def branch_n_bound(value,weight,capacity):
        global highest,size
        size=0
        room=capacity
        density = [0] * len(items)
        highest = 0
        for i in range(n):
            density[i] = val[i] / weight[i]
        for i in range(n):
            a=density.index(max(density))
            if weight[a]<=room:
                room-=weight[a]
                highest+=value[a]
                size+=weight[a]
                taken[a]=1
                del density[a], weight[a], value[a]
            else:
                break

Answer 1

我认为您尝试解决的问题可以通过更改数据结构更容易地解决。您可以构建一个元组数组 [(density, weight, value)...] 并将您的解决方案基于该数组，而不是构建密度数组。如果您不想使用太多额外内存并假设您可以更改输入数据，则可以将索引标记为已删除 - 例如，您可以将值、权重和密度设置为负数以了解该数据已从该索引中删除。

你也可以看看heapq数据结构：https://docs.python.org/3/library/heapq.html。您可以使用堆来提取最大值，并将索引存储在该堆中。

以正确的顺序选择列表中价值最高的项目

Selecting items with highest value in a list with the right order

python

list

for-loop

knapsack-problem

branch-and-bound