Artikel berechnen in Zweig und gebundenen Rucksack

Question

Mit einem Zweig-und-Grenze-Algorithmus habe ich den optimalen Gewinn aus einer bestimmten Menge von Elementen ausgewertet, aber jetzt möchte ich herausfinden, welche Elemente in dieser optimalen Lösung enthalten sind. Ich bin Bewertung der Gewinnwert des optimalen Tornister wie folgt (angepasst von 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 wie kann ich die Einzelteile erhalten, die die optimale Lösung, anstatt nur den Gewinn bilden?

Answer 1

Ich habe seit einiger Zeit darüber nachgedacht. Offensichtlich müssen Sie einige Methoden innerhalb Ihrer Node-Klasse hinzufügen, die den Knoten_Pfad zuweisen und ihm die aktuelle Ebene hinzufügen. Sie rufen Ihre Methoden innerhalb Ihrer Schleife auf und weisen die Pfad_Liste Ihrer optimal_item_list zu, wenn Ihr Knoten_gewicht kleiner als die Kapazität ist und sein Wert größer ist als der max_profit, dh wo Sie den maxProfit zuweisen. Sie können die Java-Implementierung finden here

Answer 2

Ich habe dies funktioniert mit Ihrem Code als Ausgangspunkt. I definiert meine Node Klasse:

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 

ich meinen Ranzen dann Solver in ähnlicher Weise begonnen, aber initialisiert root = Node(0, 0, 0, 0.0, []). Der Wert root.bound könnte ein Float sein, weshalb ich ihn auf 0.0 initialisierte, während die anderen Werte (zumindest in meinem Problem) ganze Zahlen sind. Der Knoten enthält bisher nichts, also habe ich mit einer leeren Liste angefangen. Ich folgte einem ähnlichen Umriss, um Ihren Code, außer dass ich die Grenze in jedem Knoten gespeichert (nicht sicher, ob dies erforderlich war), und aktualisiert die contains Liste:

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 

Bitte beachte, dass ich nur die contains Liste in der aktualisierten "Nimm den Gegenstand" Knoten. Dies ist die erste Initialisierung in Ihrer Hauptschleife, die der ersten if bound > maxProfit:-Anweisung vorausgeht. Ich das Recht vor diese contains Liste in der if: Anweisung aktualisiert, wenn Sie den Wert von maxProfit aktualisieren:

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

Dieser speichert die Indizes der Elemente, die Sie bestList einnehmen. Ich fügte auch die Bedingung if v.bound > maxProfit and v.level < items-1 der Hauptschleife direkt nach v = queue.get(), so dass ich nicht weiter, nachdem ich das letzte Element zu erreichen, und ich nicht durch Zweige, die nicht zu erkunden, Schleife.

Auch, wenn Sie eine binäre Liste Ausgabe zeigt bekommen möchten, welche Elemente von Index ausgewählt werden, könnten Sie verwenden:

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

print str(taken) 

ich in meinem Code einige andere Unterschiede hatten, aber das sollte Ihnen ermöglichen, zu erhalten Ihr ausgewählter Artikel wird aufgelistet.