Drucken Sie die Werte der Rucksacklösung

Question

Ich habe die folgende Lösung für das Rucksackproblem: (wt [] ist das Gewichtungsfeld, val [] ist das Array Werte, n ist die Größe des Arrays, Index ist das aktuelle Element, das wir sind versuchen (für die Rekursion) und arr ist ein Array, das Wetter oder nicht Element darstellt, i in der Lösung enthalten war.

int knapSack(int W, int wt[], int val[], int n, int index, int arr[]) 
{ 
    if (n == index || W == 0) 
     return 0; 
    if (wt[index] > W) 
     return knapSack(W, wt, val, n, index+1); 

    int with=val[index]+knapSack(W-wt[index], wt, val, n, index+1); 
    int without=knapSack(W, wt, val, n, index+1); 

    if(with>without){ 
     arr[index]=1; 
     return with; 
    } 
    else{ 
     arr[index]=0; 
     return without; 
    } 

} 

ich versuche, die Elemente in dieser rekursiven Lösung zu drucken, die gewählt werden, um die Einstellung Indizes von den genommenen in einem Array (Res) zu 1.
Wie ich verstehe, wenn with>without, bedeutet es, dass ich den aktuellen Artikel oder den Artikel #index wähle.So warum gibt das nicht einen richtigen Wert zurück?
Ich verwende den rekursiven Algorithmus aus einem Grund, ich weiß, dass die Verwendung der Memo-Version hier einfacher sein kann. Beispiel:
Gewichte: 5 6 7 10 11
Werte: 2 4 5 6 9
W = 25
5 Einsen in Array res zurückkehren. Wenn die Lösung 18 ist mit den Elementen 2,3,5 (beginnend mit dem Index 1).

Answer 1

Premise 1: im Code, die Rekursion ruft knapSack sind arr nicht vorbei, die einen Übersetzungsfehler verursachen sollte, gehe ich davon aus, es ist nur ein copy/paste Fehler.

Premise 2: mit den Daten, die Sie, der resultierende arr Wert nicht all 1 ist vorgeschlagen, wie Sie angedeutet, aber 01011, die immer noch nicht korrekt ist.

Betrachten wir die hypothetische Situation, in der während der Ausführung Ihrer Funktion, with größer als without: während der with Berechnung arr mit den korrekten Werten gefüllt ist; Starten Sie dann aber die without Berechnung, die die Werte arr überschreiben wird.

Da with größer als without ist, wird die zurückgegebene arr die falsche sein, und dies ist die Ursache des Problems.

wäre eine einfache Lösung eine Kopie der arr durch die with Berechnung zurückgegeben zu machen sein, so dass es durch die without Berechnung nicht überschrieben wird werden, zum Beispiel:

int with=val[index]+knapSack(W-wt[index], wt, val, n, index+1, arr); 

// copy the "with" arr 
int arrWith[n]; 
copyArr(arr, arrWith, n); 

int without=knapSack(W, wt, val, n, index+1, arr); 

if(with>without){ 
    // restore the "with" arr 
    copyArr(arrWith, arr, n); 

    arr[index]=1; 
    return with; 
} 
else{ 
    arr[index]=0; 
    return without; 
} 

copyArr ist einfach:

void copyArr(int arr[], int arrDest[], int n) { 
    int i; 
    for(i = 0; i < n; i++) { 
     arrDest[i] = arr[i]; 
    } 
} 

Mit diesem Fix ist der resultierende Wert von arr korrekt 01101.