0

我正在使用我现在正在研究的分支定界算法来解决背包问题。在算法中，我想开始选择密度（值/重量）最高的项目。我创建了一个名为“密度”的列表并进行了必要的计算。我每次都需要从该列表中选择最大值。但是每次我尝试时，订单都会变得混乱。我需要更新变量“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
4

1 回答 1

1

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

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

于 2020-08-18T20:13:22.607 回答