Calcolo degli articoli inclusi nello zaino diramato e legato

Question

Utilizzando un algoritmo derivato e associato ho valutato il profitto ottimale da un determinato insieme di elementi, ma ora desidero scoprire quali articoli sono inclusi in questa soluzione ottimale. Sto valutando il valore di profitto dello zaino ottimale nel modo seguente (adattato da 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 

Così, come posso ottenere gli elementi che costituiscono la soluzione ottimale, piuttosto che solo il profitto?

Answer 1

Ci ho pensato per un po 'di tempo. Apparentemente, devi aggiungere alcuni metodi all'interno della classe Node che assegneranno il nodo_path e aggiungeranno il livello corrente ad esso. Chiami i tuoi metodi all'interno del tuo loop e assegni il path_list a optimal_item_list quando il tuo nodo weight è inferiore alla capacità e il suo valore è maggiore del max_profit, cioè dove assegni il maxProfit. È possibile trovare l'implementazione java here

Answer 2

Ho ottenuto questo funzionamento utilizzando il codice come punto di partenza. Ho definito la mia classe Node come:

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 

Poi ho iniziato la mia bisaccia risolutore in modo simile, ma initalized root = Node(0, 0, 0, 0.0, []). Il valore root.bound potrebbe essere un float, motivo per cui l'ho initalizzato su 0.0, mentre gli altri valori (almeno nel mio problema) sono tutti numeri interi. Il nodo non contiene nulla finora, quindi l'ho avviato con una lista vuota. Ho seguito uno schema simile al codice, se non che ho memorizzato il limite in ciascun nodo (non sono sicuro che questo era necessario), e ha aggiornato l'elenco contains utilizzando:

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 

Nota che ho solo aggiornato l'elenco contains nel nodo "prendendo l'oggetto". Questa è la prima inizializzazione nel ciclo principale, precedente alla prima dichiarazione if bound > maxProfit:. Ho aggiornato la lista contains nella dichiarazione if: destra prima di questo, quando si aggiorna il valore di maxProfit:

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

Questo memorizza gli indici delle voci che sta assumendo per bestList. Ho anche aggiunto la condizione if v.bound > maxProfit and v.level < items-1 al ciclo principale subito dopo v = queue.get() in modo che non continui dopo che ho raggiunto l'ultimo elemento e non faccio il giro dei rami che non vale la pena esplorare.

Inoltre, se si vuole ottenere un elenco binario mostra di uscita che gli elementi sono selezionati in base all'indice, è possibile utilizzare:

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

print str(taken) 

ho avuto alcune altre differenze nel mio codice, ma questo dovrebbe consentire di ottenere la tua voce scelta lista.