2016-04-19 3 views
1

Ich bin neu bei Python, vielleicht kann es eine dumme Frage sein.Rekursive Funktion gibt keine erzeugte Zeichenfolge zurück

Ich habe eine einfache rekursive Rucksacklösung implementiert, die irgendwann eine Bitsequenz zurückgibt. Aber manchmal gibt es keine Sequenz zurück, die erzeugt wird. Hier ist mein Code und seine Ergebnisse für verschiedene Eingaben.

def knapsackRecursive(items, maxNum, bestResponse): 
    print('items=' + str(items) + ', maxNum=' + str(maxNum)) 
    referenceIndex = 0 
    editableMaxNum = maxNum 
    if editableMaxNum == 0: 
     bestResponse = '0' 
    else: 
     for i in reversed(items): 
      item = int(i) 
      if editableMaxNum >= item: 
       if referenceIndex == 0: 
        referenceIndex = items.index(str(item)) 
       editableMaxNum -= item 
       bestResponse = '1' + bestResponse 
      else: 
       bestResponse = '0' + bestResponse 
     if editableMaxNum != 0: 
      bestResponse = '' 
      if referenceIndex != 0: 
       for k in range(0, len(items) - referenceIndex): 
        bestResponse = '0' + bestResponse 

       knapsackRecursive(items[:referenceIndex], maxNum, bestResponse) 
      else: 
       bestResponse = '0' 

    print('bestResponse=' + str(bestResponse)) 
    return bestResponse 

Items Konstanten sind, die [ '1', '2', '4', '10', '20', '40', '63', '105']. Auch initial bestResponse ist eine leere Zeichenfolge.

wenn ich maxNum als 41 eingestellt, Ausgabe lautet:

items=['1', '2', '4', '10', '20', '40', '63', '105'], maxNum=41 
bestResponse=10000100 

Aber wenn ich maxNum als 71 gesetzt, Ausgabe lautet:

items=['1', '2', '4', '10', '20', '40', '63', '105'], maxNum=71 
items=['1', '2', '4', '10', '20', '40'], maxNum=71 
bestResponse=10011100 
bestResponse=00 

Warum bestResponse Ausgabe gedruckt zweimal für Eingang 71? Und obwohl der erste Druck richtig ist, warum gibt die Funktion das zweite Ergebnis zurück, das falsch ist?

EDIT

Ich habe knapsackRecursive(items[:referenceIndex], maxNum, bestResponse) als return knapsackRecursive(items[:referenceIndex], maxNum, bestResponse) geändert. Es scheint gelöst zu sein. Offensichtlich habe ich einen Fehler gemacht, wenn ich rekursiv benutze. Aber trotzdem konnte ich nicht verstehen, warum die Funktion das Ergebnis des ersten Anrufs anstelle des zweiten Anrufs zurückgibt, von dem erwartet wird, dass er die richtige Antwort erzeugt.

Antwort

1

Ich glaube, Sie tun sollten:

best_response = knapsackRecursive(items[:referenceIndex], maxNum, bestResponse) 

statt

knapsackRecursive(items[:referenceIndex], maxNum, bestResponse)