Geek asks and answers

Calculation of items included in the hanger and associated backpack

Using a branching and related algorithm, I estimated the optimal profit from this set of elements, but now I want to find out which elements are included in this optimal solution. I estimate the profit value of the optimal satchel as follows (adapted from here ):

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

So, how can I get the elements that form the optimal solution , and not just profit?

+5
source share
2 answers

I got this working using your code as a starting point. I defined my class Nodeas:

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 float, 0.0, ( , ) . node , . , , node ( , ) 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 " " node. , 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)

, .

+3

. -, Node, node_path . path_list optim_item_list, node_weight , , max_profit, maxProfit. java

+2

More articles:


All Articles