algo:knapsack - Backtracking

[nufan]

Sorry, dass ich mich jetzt erst zu Wort melde. Ich hatte den Thread den ganzen Tag offen, bin aber erst jetzt zum Antworten gekommen.

Damit landen dann die Gegenstände 2, 5 und 9 im Rucksack.

Kann es sein, dass die Tabelle im Wiki-Artikel einen Fehler hat?

Code: Alles auswählen

15	 -1	 -1	 -1	 -1	 -1	->20	30<-	30	30	 0

Wenn dein Algorithmus da durch läuft, dann müsste es doch 30-30 sein?

Nein, statt 3 mal 30 sollte dort immer 20 stehen. Siehe auch in der Tabelle darüber, die eigentlich die genau gleiche ohne grüne Markierung ist. Scheint ein Copy&Paste-Fehler zu sein und ist ausgebessert.

Code: Alles auswählen

if( results[i][currentVolume] != results[i + 1][currentVolume] )
{
  // Gegenstand war im Rucksack
  fprintf( stdout, "selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
  currentVolume -= v[i];
}

[...]
Meine Frage ist nur, ob ich richtig liege und das so auch korrekt ist, oder ob meine Variante nur zufällig bei den Eingabewerten, die ich getestet habe (incl. denen aus dem Tutorial) funktioniert, und mir bei anderen um die Ohren fliegen kann.

Ich hab jetzt nur kurz drüber nachgedacht, aber ich denke es sollte gehen. Wobei du bei Mehrfachlösungen immer eine andere Lösung als der Algorithmus im Wiki bekommen wirst (im Wiki werden niedrigere Indizes bevorzugt, bei dir hohe Indizes). Deine Lösung ist technisch einfacher, aber ich finde die Analogie mit dem Herausnehmen erleichtert das Verständnis etwas.

Sehr gute Idee. Hab ich direkt mal gemacht (http://codepad.org/s0jb6ilB).
Dabei sieht man tatsächlich, dass es Fälle gibt, in denen beide Verfahren unterschiedliche Ergebnisse liefern!
Als ich mir ein paar einfache Fälle von Hand angucken wollte, ist mir allerdings aufgefallen, dass der Algorithmus aus dem Tutorial oft in undefiniertes Verhalten läuft. Z.b mit folgenden Testdaten:

Code: Alles auswählen

5 2
17 13
3 13

gilt in dieser Zeile

Code: Alles auswählen

if( r - w[i] == results[i + 1][currentVolume - v[i]] )

Code: Alles auswählen

currentVolume - v[i] == -12

und dann kann ja bekanntlich irgendwas passieren (http://codepad.org/oGIwQSRH).
Ich konnte also leider nicht überprüfen, ob mein Verfahren korrekt läuft, weil das gegebene bereits fehlerhaft ist.

Als ich gerade versucht habe, diese Abfrage einzubauen, ist mir ein weiterer Fehler im Tutorial-Code aufgefallen. In den Beispieldaten sind 10 Objekte, das Backtracking schaut den letzten aber nie an.

Code: Alles auswählen

selecting 1 (5 / 8)
NOT selecting 2 (5 / 8)
NOT selecting 3 (6 / 6)
NOT selecting 4 (8 / 5)
selecting 5 (10 / 10)
NOT selecting 6 (11 / 5)
NOT selecting 7 (12 / 10)
NOT selecting 8 (15 / 17)
selecting 9 (15 / 20)

Da fehlt also ein

Code: Alles auswählen

NOT selecting 10 (30 / 20)

Wenn Gegenstand 10 in den Rucksack gehören würde, würde er ihn also nicht reintun.

So ganz einfach lösen konnte ich das aber auch nicht, denn einfach aus dem hier

Code: Alles auswählen

for( int i = 0; i < n-1; i++ )

das hier

Code: Alles auswählen

for( int i = 0; i < n; i++ )

machen, geht auch nicht, weil man dann beim Index über die Arraygrenzen hinaus liest.

Hm.. stimmt.

Die negativen Zugriffe hab ich durch eine einfache Prüfung im if verhindert.

Bezüglich des letzten Elements:
Da "r" ja die maximale Summe aller Gegenstände im Rucksack ist, kann ich das relativ leicht prüfen. Ich subtrahiere in der obigen Schleife alle Gegenstände von "r" und muss entsprechend auf 0 kommen. Ist mein "r" nach allen Elementen außer dem letzten nicht 0, dann wurde der Gegenstand ausgewählt (und "r" muss entsprechend den gleichen Wert wie der letzte Gegenstand haben).

Was sagt ihr dazu:

Code: Alles auswählen

    if( currentVolume - v[i] >= 0 && r - w[i] == results[i + 1][currentVolume - v[i]] )
    {
      fprintf( stdout, "selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
      r -= w[i];
      currentVolume -= v[i];
    }
    else
      fprintf( stdout, "NOT selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
  }
  if( r > 0 )
    fprintf( stdout, "selecting %d (%d / %d)\n", n, v[n - 1], w[n - 1] );
  else
    fprintf( stdout, "NOT selecting %d (%d / %d)\n", n, v[n - 1], w[n - 1] );

Vielleicht sollte nufan den Backtracking-Teil also nochmal überarbeiten.

Sieht wohl so aus ^^ Vielen Dank für das Feedback. Ich würde vorschlagen wir diskutieren in diesem Thread alle Fehler aus, überlegen uns eventuell noch ein zweites Beispiel und ich pack das ganze dann ins Wiki.

[Dobias]

Vielen Dank für die ausführliche Antwort. Schön, dass unsere Backtracking-Verfahren beide funktionieren.
Um dies dann zu verifizieren, hab ich nochmal beide auf vielen Eingaben gegeneinander verglichen ( http://codepad.org/Aoeappir ). Sie waren sich immer einig.
(Sorry, dass ich deinen Code dafür so umgeschrieben hab, aber so wars für mich einfacher zu lesen. Besonders "v" und "w" hat mich verwirrt, weil ich immer an *V*alue und *W*eight anstatt *V*olumen und *W*ert gedacht hab. )
(Das Ganze in Haskell, falls jemans Interesse hat: http://lpaste.net/4197437543714652160 Hier wird zusätzlich auch die naive Rekursive Variante mit beiden BT-Verfahren verglichen, was auch immer zum gleichen Wertsumme im Rucksack führt.)

[cloidnerux]

Das Ganze in Haskell, falls jemans Interesse hat:

http://xkcd.com/1312/

[Dobias]

Ich hab mich anfangs auch eher geweigert, weil es einfach alles so fremd war. Aber jetzt seit ich mich mal ein Bischen dran gewöhnt habe, gefällt es mir total super.
Über meine Erfahrung beim Lernen hab ich hier etwas geschrieben, falls es jemanden interessiert:
https://github.com/Dobiasd/articles/blo ... _in_Elm.md
(Elm ist ziemlich haskellig. )

[nufan]

Ich hab die restlichen Fehler im Wiki korrigiert und einen Link hierher gesetzt.

[Dobias]

Super, sieht gut aus.