计算分支和绑定背包中包含的项目

Question

使用分支定界算法,我已经评估了给定项目集的最佳利润,但现在我想知道哪个项目包含在这个最优解决方案中.我正在评估最佳背包的利润值如下(从这里改编):

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 

那么,我如何才能获得构成最佳解决方案的项目,而不仅仅是利润？

Answer 1

我已经思考这个问题有一段时间了。显然，您必须在 Node 类中添加一些方法来分配 node_path 并向其添加当前级别。当您的node_weight小于容量并且其值大于max_profit（即您分配maxProfit的位置）时，您在循环内调用您的方法并将path_list分配给optimal_item_list。你可以在这里找到java实现