bwinf/ subset-sum

[Gast]

Hallo,

ein Teil der ersten Aufgabe ist offensichltich ein subset-sum Problem, man muss eine Teilmenge M einer Menge N finden, deren Summe am nächsten an einer ganzen Zahl c ist.

Nun ist das subset-sum Problem aber NP-hart und nur in exponentieller Zeit zu lösen.

Als Beispiele werden aber mehr als 500 zu kaufende Gegenstände gegeben -
wie sollte das lösbar sein ? Das ist doch in absehbarer Zeit unmöglich ??


Aufgaben : http://www.bwinf.de/index.php?id=149
ein zu lösended Beispiel : http://www.bwinf.de/uploads/media/beispiel3_01.txt

[Stone2001]

Lösen kann man sowas mit z.B. Simulated Annealing oder Genetischen Algorithmen. Man bekommt dann zwar suboptimale Lösungen, diese sind aber in der Regel recht gut und man bekommt sie recht schnell.

[Gast]

Nein, es heisst in der Aufgabenstellung "Dabei MUSS eine kleinstmögliche Anzahl von Monaten verwendet werden"

[Stone2001]

Wenn sie wirklich die kleinstmögliche Anzahl an Monaten wollen, dann bleibt dir wohl nichts anderes übrig, als das NP-Problem zu lösen. (Yeah, "Brute Force") Würde mich mal interessieren, wie lange die Berechnung für die Beispieldatei dauert.
Alle anderen Lösungswege, die ich gerade im Kopf habe, garantieren nicht die beste Lösung.

[ethrandil]

Interessantes Problem :D Gibts die Aufgaben online??

- eth

[Gast]

http://www.bwinf.de/index.php?id=149



Sry, online glaub' ich ned........

die anderen Aufgaben sind aber auch viel leichter.....
bzw. eigentlich ist diese auch ned schwer....für wenige Zahlen....

[Gast]

Würde mich mal interessieren, wie lange die Berechnung für die Beispieldatei dauert.


Naja ich hab's bis jetzt absolut brute Force, also ist die Dauer O(2^NN), gibt aber auch Algorithmen für O(2^(N/2) N)...

Naja .... 2^500 ist schon ne große Zahl :-0

[Senior Sanchez]

Natürlich gibts die Aufgaben online: http://bwinf.de/uploads/media/bwinf251-einfach.pdf

Aber @Gast: Bitte poste hier nicht deine Lösungsstrategie, es ist einfach irgendwo unfair und jeder soll sich selber Gedanken machen.

Achja, noch als kleiner Tipp: Das ist die erste Runde und da sind die Lösungen meist sehr einfach oder "trivial", also denke da nicht zu kompliziert. Du kannst deine Bedenken aber in der Doku erwähnen, nur wird dir das in der ersten Runde keine Zusatzpunkte bringen.

Falls de inne zweite Runde kommst, da kannste dann schon mehr deine Klasse zeigen ;)

Und falls du es in die Endrunde schaffen solltest, viel Spaß :)
Ich war bei der letzten in Aachen dabei und es war absolut genial! (Was vllt auch mit daran lag weil ich Preisträger wurde ;) )

[Trap]

Allgemein lassen sich NP-schwere Probleme oft effizient mit dynamischer Programmierung (dynamic programming) lösen, wenn man feste Obergrenzen gegeben hat und genug Speicher für die Tabelle hat.

Subset-sum ist aber das falsche Problem, man muss nicht für jeden Wert prüfen ob man soviel ausgeben kann, sondern will soviel wie möglich ausgeben, aber maximal 1000€.