AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Beste Kombination zur Auffüllung einer Liste

Ein Thema von Valle · begonnen am 3. Jul 2013 · letzter Beitrag vom 4. Jul 2013
 
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
11.757 Beiträge
 
Delphi 12 Athens
 
#8

AW: Beste Kombination zur Auffüllung einer Liste

  Alt 3. Jul 2013, 16:08
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.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:09 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz