Beste Kombination zur Auffüllung einer Liste

[Uwe Raabe]

Die Aufgabestellung hat gewisse Ähnlichkeiten mit dem Rucksack-Problem, bei dem möglichst viele Dinge in den Rucksack gepackt werden sollen ohne ihn zu überfüllen. Die Unterschiede sind

a) die Dinge (Listen) sind in beliebiger Anzahl verfügbar
b) der Rucksack soll ganz voll sein

In diesem Fall bietet sich eine kombinatorische Lösung an. Dabei wird eine Liste in den Rucksack aufgenommen und der daraus resultierende Status überprüft. Ist der Rucksack noch nicht voll, mache ich einfach so weiter. Andernfalls habe ich entweder eine Lösung gefunden (Rucksack ist genau voll) oder der Rucksack ist überfüllt. In beiden Fällen muss ich die zuletzt eingepackte Liste wieder herausnehmen und nehme mir die nächste Liste. Bin ich nun bei der letzten Liste angekommen, nehme ich alle Vorkommen dieser letzten Liste raus. die dann "oberste" Liste nehme ich auch heraus und verfahre so, als ob der Rucksack voll gewesen wäre. Das ganze Spiel geht solange weiter bis ich nur noch Elemente der letzten Liste im Rucksack habe.

Konkret anhand der Beispieldaten:

L0 = [3, 2, 0]
L1 = [0, 0, 2]
L2 = [0, 0, 1]
L3 = [4, 0, 0]

Lösungsbedingung: [3, 2, 4]

Anfangszustand Rucksack: ()|[0,0,0] { leer }

1. (L0) [3,2,0]
2. (2*L0) [6,4,0] // überfüllt
3. (L0+L1) [3,2,2]
4. (L0+2*L1) [3,2,4] // Lösung
5. (L0+L1+L2) [3,2,3]
6. (L0+L1+2*L2) [3,2,4] // Lösung
7. (L0+L1+L3) [7,2,0] // überfüllt, L3 ist letzte Liste
8. (L0+L2) [3,2,1]
9. (L0+2*L2) [3,2,2]
10. (L0+3*L2) [3,2,3]
11. (L0+4*L2) [3,2,4] // Lösung
12. (L0+3*L2+L3) [7,2,3] // überfüllt, L3 ist letzte Liste
13. (L0+2*L2+L3) [7,2,2] // überfüllt, L3 ist letzte Liste
14. (L0+L2+L3) [7,2,1] // überfüllt, L3 ist letzte Liste
15. (L1) [0,0,2]
16. (2*L1) [0,0,4]
17. (3*L1) [0,0,6] // überfüllt
18. (2*L1+L2) [0,0,5] // überfüllt
19. (L1+L2) [0,0,3]
20. (L1+2*L2) [0,0,4]
21. (L1+3*L2) [0,0,5] // überfüllt
22. (L1+2*L2+L3) [4,0,4] // überfüllt, L3 ist letzte Liste
23. (L1+L2+L3) [4,0,3] // überfüllt, L3 ist letzte Liste
24. (L2) [0,0,1]
25. (2*L2) [0,0,2]
26. (3*L2) [0,0,3]
27. (4*L2) [0,0,4]
28. (5*L2) [0,0,5] // überfüllt
29. (4*L2+L3) [4,0,4] // überfüllt, L3 ist letzte Liste
30. (3*L2+L3) [4,0,3] // überfüllt, L3 ist letzte Liste
31. (2*L2+L3) [4,0,2] // überfüllt, L3 ist letzte Liste
32. (L2+L3) [4,0,1] // überfüllt, L3 ist letzte Liste
33. (L3) [4,0,0] // überfüllt, L3 ist letzte Liste, Ende der Kombinationen

Man kann das noch optimieren, in dem man alle Listen gleich raus wirft, die schon alleine zu einer Überfüllung führen. Dann spart man sich einen Haufen Iterationen.