Knapsack rekursive Funktion

Question

Ich habe eine Liste mit dem Namen self.items, wo die Elemente sind:

items = [dict(id=0, w=4, v=12), 
     dict(id=1, w=6, v=10), 
     dict(id=2, w=5, v=8), 
     dict(id=3, w=7, v=11), 
     dict(id=4, w=3, v=14), 
     dict(id=5, w=1, v=7), 
     dict(id=6, w=6, v=9)] 

Damit ich eine Liste von Listen zu tun hatte, in dem jedes Element alle möglichen Kombinationen, einschließlich der leeren Fall hat, so endlich meine Liste der Listen hat mehr oder weniger dieses Aussehen:

[[],[{id:0,w:4,v:12}],....,[{id:0,w:4,v:12}, {id:1,w:6,v:10}]....] 

Jetzt muss ich eine rekursive Funktion zur Suche gefunden, welche Kombination von Elementen, die max Gewicht erlaubt und den Maximalwert.

def recursive(self, n, max_weight): 
""" Recursive Knapsack 
:param n: Number of elements 
:param max_weight: Maximum weight allowed 
:return: max_value 
""" 
self.iterations += 1 
result = 0 

if max_weight > self.max_weight: #they gave me self.max_weight as a variable of __init__ method which shows me what is the maximum weight permitted 
    self.recursive(self, self.items+self.iterations, max_weight) 
    if max_weight < self.max_weight: 
     self.recursive(self, self.items+self.iterations, max_weight) 
    else: 
      result = self.items['v']+result 

return result 

Ich denke, dass meine Fehler in dieser Zeile ist:

result = self.items['v']+result 

Aber ich kann es nicht finden.

Answer 1

ich die Lösung nur auf dieses rekursive Problem gefunden habe: (I aus Spanien ist so wird die Variable "cantidad" bedeutet auch "Quantität")

def recursive(self, n, max_weight): 
    """ Recursive Knapsack 
    :param n: Number of elements 
    :param max_weight: Maximum weight allowed 
    :return: max_valu 
    """ 
    self.iterations += 1 
    result = 0 
    cantidad = 0 
    quantity = 0 

    if max_weight == 0 or n == 1: 
     if max_weight >= self.items[n-1]['w'] : 
      cantidad= self.items[n-1]['v'] 

     return max(cantidad,quantity) 
    else: 
     if max_weight >= self.items[n-1]['w']: 
      cantidad = self.items[n-1]['v']+self.recursive(n-1,max_weight-self.items[n-1]['w']) 

     quantity = self.recursive(n-1,max_weight) 
     result = max(cantidad, quantity) 
     return result 

ich diesen Code in ein Programm setzte proportioniert durch die Universität, an der ich studiere, und sie gibt mir das korrekte Ergebnis zurück:

Method: recursive 
Iterations:107 
Max value:44 expected max_value:44