Re: algo:knapsack - Backtracking
Verfasst: Mo Feb 17, 2014 9:11 pm
Sorry, dass ich mich jetzt erst zu Wort melde. Ich hatte den Thread den ganzen Tag offen, bin aber erst jetzt zum Antworten gekommen.
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:
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.cloidnerux hat geschrieben:Kann es sein, dass die Tabelle im Wiki-Artikel einen Fehler hat?Damit landen dann die Gegenstände 2, 5 und 9 im Rucksack.Wenn dein Algorithmus da durch läuft, dann müsste es doch 30-30 sein?Code: Alles auswählen
15 -1 -1 -1 -1 -1 ->20 30<- 30 30 0
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.Dobias hat geschrieben:[...]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.
Dobias hat geschrieben: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:gilt in dieser ZeileCode: Alles auswählen
5 2 17 13 3 13
Code: Alles auswählen
if( r - w[i] == results[i + 1][currentVolume - v[i]] )
und dann kann ja bekanntlich irgendwas passieren (http://codepad.org/oGIwQSRH).Code: Alles auswählen
currentVolume - v[i] == -12
Ich konnte also leider nicht überprüfen, ob mein Verfahren korrekt läuft, weil das gegebene bereits fehlerhaft ist.
Hm.. stimmt.Dobias hat geschrieben: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.Da fehlt also einCode: 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)
Wenn Gegenstand 10 in den Rucksack gehören würde, würde er ihn also nicht reintun.Code: Alles auswählen
NOT selecting 10 (30 / 20)
So ganz einfach lösen konnte ich das aber auch nicht, denn einfach aus dem hierdas hierCode: Alles auswählen
for( int i = 0; i < n-1; i++ )
machen, geht auch nicht, weil man dann beim Index über die Arraygrenzen hinaus liest.Code: Alles auswählen
for( int i = 0; i < n; i++ )
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] );
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 hat geschrieben:Vielleicht sollte nufan den Backtracking-Teil also nochmal überarbeiten.