Beispiel warum Greedy mit Ganzzahliger Mitnahme von Gegenständen nicht optimal ist
Rucksackgröße 15
| Obj | Wert | Gewicht | rDB |
|---|---|---|---|
| A | 8 | 4 | 2 |
| B | 5 | 3 | 1.67 |
Angenommen wir würde nur den Gegenstand mit besten rDB (relativer Deckungsbeitrag = Wert / Gewicht)
mitnehmen, bis kein Platz mehr da ist. Dann würde man 3 Stück A mitnehmen und hätte noch 1 Gewicht
im Rucksack frei, wo wir nichts mehr reinpacken könnten. Der Gesamtwert wäre somit 24.
Würde man (nicht greedy) stattdessen nur B einpacken, könnte man 5 Stück mitnehmen und hätte keinen Platz
mehr im Rucksack übrig. Der Gesamtwert wäre somit 25, was besser als 24 bei der Greedy Variante wär.
Greedy:
| Obj | Wert | Gewicht | rDB | Stück | übrig | Gesamtwert |
|---|---|---|---|---|---|---|
| A | 8 | 4 | 2 | 3 | 1 | 24 |
Nicht Greedy:
| Obj | Wert | Gewicht | rDB | Stück | übrig | Gesamtwert |
|---|---|---|---|---|---|---|
| B | 5 | 3 | 1.67 | 5 | 0 | 25 |