5

使用分支定界算法，我已经评估了一组给定项目的最佳利润，但现在我希望找出哪些项目包含在这个最优解决方案中。我正在评估最佳背包的利润值如下（改编自此处）：

import Queue

class Node:
    def __init__(self, level, profit, weight):
        self.level = level # The level within the tree (depth)
        self.profit = profit # The total profit
        self.weight = weight # The total weight

def solveKnapsack(weights, profits, knapsackSize):
    numItems = len(weights)
    queue = Queue.Queue()
    root = Node(-1, 0, 0)    
    queue.put(root)

    maxProfit = 0
    bound = 0
    while not queue.empty():
        v = queue.get() # Get the next item on the queue

        uLevel = v.level + 1 
        u = Node(uLevel, v.profit + e[uLevel][1], v.weight + e[uLevel][0])

        bound = getBound(u, numItems, knapsackSize, weights, profits)

        if u.weight <= knapsackSize and u.profit > maxProfit:
            maxProfit = uProfit

        if bound > maxProfit:    
            queue.put(u)

        u = Node(uLevel, v.profit, v.weight)
        bound = getBound(u, numItems, knapsackSize, weights, profits)

        if (bound > maxProfit):
            queue.put(u)
    return maxProfit

# This is essentially the brute force solution to the fractional knapsack
def getBound(u, numItems, knapsackSize, weight, profit):
    if u.weight >= knapsackSize: return 0
    else:
        upperBound = u.profit
        totalWeight = u.weight
        j = u.level + 1
        while j < numItems and totalWeight + weight[j] <= C:
            upperBound += profit[j]
            totalWeight += weights[j]
            j += 1
        if j < numItems:
            result += (C - totalWeight) * profit[j]/weight[j]
        return upperBound

那么，我怎样才能得到构成最优解的项目，而不仅仅是利润呢？

4

2 回答 2

3

我使用您的代码作为起点来完成这项工作。我将我的Node班级定义为：

class Node:
    def __init__(self, level, profit, weight, bound, contains):
        self.level = level          # current level of our node
        self.profit = profit
        self.weight = weight        
        self.bound = bound          # max (optimistic) value our node can take
        self.contains = contains    # list of items our node contains

然后我同样启动了我的背包求解器，但初始化了root = Node(0, 0, 0, 0.0, []). 该值root.bound可能是一个浮点数，这就是为什么我将它初始化为0.0，而其他值（至少在我的问题中）都是整数。到目前为止，该节点不包含任何内容，因此我从一个空列表开始。我遵循了与您的代码类似的大纲，除了我将绑定存储在每个节点中（不确定这是必要的），并contains使用以下方法更新列表：

u.contains = v.contains[:]    # copies the items in the list, not the list location
# Initialize u as Node(uLevel, uProfit, uWeight, 0.0, uContains)
u.contains.append(uLevel)    # add the current item index to the list

请注意，我只更新了contains“获取项目”节点中的列表。这是主循环中的第一个初始化，在第一条if bound > maxProfit:语句之前。当您更新以下值时，我在此之前更新contains了语句中的列表：if:maxProfit

if u.weight <= knapsackSize and u.value > maxProfit:
    maxProfit = u.profit
    bestList = u.contains

这存储了您要访问的项目的索引bestList。if v.bound > maxProfit and v.level < items-1之后我还在主循环中添加了条件，v = queue.get()这样我就不会在到达最后一项后继续前进，也不会循环遍历不值得探索的分支。

此外，如果您想获得一个二进制列表输出，显示哪些项目是按索引选择的，您可以使用：

taken = [0]*numItems
for item in bestList:
    taken[item] = 1

print str(taken)

我的代码中还有其他一些差异，但这应该使您能够获得您选择的项目列表。

于 2013-07-06T19:07:38.420 回答
2

我一直在考虑这个问题。显然，您必须在 Node 类中添加一些方法，这些方法将分配 node_path 并将当前级别添加到其中。当您的 node_weight 小于容量并且它的值大于 max_profit 时，您在循环中调用您的方法并将 path_list 分配给您的 optimization_item_list，即您分配 maxProfit 的位置。你可以在这里找到java实现

于 2013-06-27T17:39:40.930 回答