Allen NP-vollständigen Problemen ist gemeinsam, dass sie NP-vollständig sind; daher heißen sie ja so ...
Die Unterschiede sind marginal, da in polynomialer Zeit aufzählbar

Scherz beiseite.

@delfiphan: Bitte unterscheide zwischen allgemeinem und speziellen Rucksack-Problem; beim Allgemeinen durfte man nämlich Gegenstände auch mehrfach nehmen.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ich habe den selben Algorithmus, jedoch als Tiefensuche implementiert.

Der Nachteil dabei ist, dass ich bei einer Lösung nicht sofort sagen kann, dass sie minimal ist. Auf der anderen Seite verbraucht der Algorithmus von BenBE mit der Laufzeit exponentiell viel Speicher; bei mir bleibt er konstant. Dafür kann BenBE die Berechnung abbrechen, sobald er eine Lösung hat - da die erste automatisch minimal ist. Es ist aber nicht so, dass mein Algorithmus alle Lösungen wirklich durchprobieren muss, sondern man kann da einiges weglassen. Bei der Zahl 78 wird insgesamt 463x die Summe auf den Totalwert geprüft, bei BenBE sind es 3463. Bestimmt lassen sich aber beide Varianten noch optimieren

Bei mir kann allein mit der Reihenfolge der Münzen in der Eingabe schon der Suchvorgang stark optimiert werden, da damit die Summe schneller anwächst. Eine Optimierung bei mir wäre z.B. die Summe direkt im Schleifendurcklauf mitzuberechnen für den nächsten Schritt; dann wäre das Berechnen der Summe nämlich in O(1) statt O(n) möglich.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Wie wärs mit einer Suchtiefenbegrenzung wenn amn alle durchtestet.
Zuerst sucht der algo bis er die erste lösung gefunden hat, die zb aus 8 münzen besteht.
alle weiteren suchen führt er nur bis zu einer suchtiefe von 7 münzen durch.
findet er eine weitere mit 5 münzen, wird alles über einer suchtiefe von 4 ignoriert.
alternativ könnte man auch bis zur suchtiefe der besten gefundnenen konstellation gehn um
mehrere treffer mit gleicher anzahl auszugeben.