Quelle: uni-jena.de
Machen wir einen kurzen Exkurs zu eurer Sparbüchse: Stellt euch vor ihr wollt wissen, wie viel Geld ihr besitzt, seid aber viel zu faul die Münzen zu zählen (es sind sehr sehr viele Münzen — ihr seid Dagobert Duck und eure Sparbüchse ist eigentlich ein Geldspeicher). Was könnt ihr tun? Schnappt euch einfach eine Waage! Jede Euro Münze hat ein bestimmtes Gewicht. Exakt wird eure Berechnung, wenn ihr die Münzen vorher sortiert. Aber wie gesagt, ihr seid faul (vermutlich seid ihr Informatiker). Also brauchen wir einen Algorithmus, der uns das gemessene Gewicht zerlegt, in die Anzahl der enthaltenen Münzen, sortiert nach Münzarten. Das zugrunde liegende Problem ist als Münzproblem bekannt. Dabei geht es eigentlich um Wechselgeld: Mit welchen Münzen lässt sich ein Betrag x herausgeben? Algorithmisch gesehen steckt dahinter das gleiche Problem, wie bei unserer Geldwaage, wobei Wechselgeldbetrag=Gewicht des gesamten Geldes, Münzbeträge=Gewicht der Münzen. Das Münzproblem gehört zu den Rucksackproblemen, einer Gruppe der klassischen NP-vollständigen Probleme aus der theoretischen Informatik.