Frage von KaiRo1976, 42

Frankiert wurden insgesamt 2270,80€, Mögliche Teiler sind 0,70€, 0.85€, 1,45€ und 2,60€, Es dürfen aber nur 3038 Sendungen sein, also wieviel pro Teiler?

Antwort
von NoHumanBeing, 27

I) 0.7 * w + 0.85 * x + 1.45 * y + 2.6 * z = 2270.8

II) w + x + y + z = 3038

Das ist ein lineares Gleichungssystem, das allerdings unterbestimmt ist. (Zwei Gleichungen, vier Unbekannte.)

Das wird keine eindeutige Lösung geben.

Sieht auch irgendwie nach Knapsack-Problem aus, wenn w, x, y, z aus Z sind. Das wäre dann sogar NP-vollständig.

Ich habe die Beträge mal um 100 "hochskaliert" (um die Kommazahlen loszuwerden) und dann folgendes Python-Programm darauf angesetzt.

for w in range(0, 3039):
print "w = " + str(w) + " / 3038"

for x in range(0, 3039 - w):

for y in range(0, 3039 - (w + x)):
z = 3038 - (w + x + y)

if 70 * w + 85 * x + 145 * y + 260 * z == 227080:
print (w, x, y, z)

Das wird allerdings ein paar Stunden rechnen.

Ich sehe keinen Weg, das "im Kopf" (oder "schriftlich" - jedenfalls ohne Computersoftware) zu rechnen. Als NP-vollständiges Problem ist das nur per "number crunching" zu lösen.

Wenn ich eine Lösung habe (oder festgestellt, dass keine existiert), melde ich mich.

Kommentar von NoHumanBeing ,

Ok, also wie ich bereits vermutet habe, gibt es sehr viele Lösungen für dieses Problem.

Weil eine erschöpfende Liste viel zu lang wäre (es gibt einige tausend mögliche Kombinationen), schreibe ich einfach einmal ein paar Beispiele hin.

2100 * 0.70 € + 936 * 0.85 € + 0 * 1.45 € + 2 * 2.60 € = 2270.80 €
2135 * 0.70 € + 898 * 0.85 € + 0 * 1.45 € + 5 * 2.60 € = 2270.80 €
2740 * 0.70 € + 159 * 0.85 € + 125 * 1.45 € + 14 * 2.60 € = 2270.80 €
2956 * 0.70 € + 4 * 0.85 € + 4 * 1.45 € + 74 * 2.60 € = 2270.80 €

Der Betrag stimmt also überall und die Gesamtzahl an Sendungen ist auch jeweils 3038.

2100 + 936 + 0 + 2 = 3038
2135 + 898 + 0 + 5 = 3038
2740 + 159 + 125 + 14 = 3038
2956 + 4 + 4 + 74 = 3038

Kommentar von NoHumanBeing ,

Hier hast Du, wie in Deinem Kompliment angefragt, eine allgemeine Lösung.

http://pastebin.com/u95s0U7J

Die Preise sind in der Liste "prices" fest definiert, können aber im Code geändert werden.

Die Anzahl der möglichen Preise ist fest auf vier festgelegt. Um mehr (oder weniger) Preise zu ermöglichen, müsste man die Schleifenstruktur anpassen.

Gesamtanzahl der Sendungen und Gesamtbetrag werden beim Ausführen des Programms vom Benutzer abgefragt.

Beachte, dass die Laufzeit mit der vierten Potenz der Anzahl der Sendungen steigt. Für eine große Anzahl an Sendungen kann das Problem unbeherrschbar werden. Während der Programmausführung wird eine Fortschrittsanzeige angezeigt. Dies ist nur ein grober Richtwert. Im Allgemeinen werden aus Gründen der Kombinatorik die "ersten" Prozente länger dauern, als die "letzten". Die Fortschrittsabschätzung ist also "zu pessimistisch". Wenn das Programm also beispielsweise einen Fortschritt von 50 % anzeigt, wird es im Allgemeinen nicht mehr so lange rechnen müssen, wie es bereits gerechnet hat.

Um das Programm auszuführen ist auf dem jeweiligen Computer ein Interpreter für Python 2 erforderlich. Konkret habe ich das Programm auf der Version 2.7.12 getestet.

Wenn Du z. B. eingibst, dass es 8 Sendungen gibt und der Gesamtbetrag 840 ct. beträgt, dann erzeugt das Programm folgende Ausgabe.

2 Loesungen gefunden.

1 * 70 ct. 6 * 85 ct. + 0 * 145 ct. + 1 * 260 ct.
5 * 70 ct. 1 * 85 ct. + 1 * 145 ct. + 1 * 260 ct.
Kommentar von NoHumanBeing ,

Achja, zwei "Fehler" habe ich noch im Code gefunden.

Das "if i > 1:" in Zeile 31 sollte eigentlich "if i > 0:" heißen (klassischer "off-by-one error") und in Zeile 34 kann zwischen dem "ct." und dem schließenden Anführungszeichen das Leerzeichen raus.

Beides betrifft aber nur die Formatierung der Ausgabe. Das Ergebnis an sich ändert sich nicht.

Kommentar von NoHumanBeing ,

Hier die überarbeitete Variante: http://pastebin.com/43inp2Ti

Kommentar von KaiRo1976 ,

vielen Dank für die Lösung.

Ich habe allerdings das Problem das ich das nicht zusammen bekomme.

Ich habe mir zuerst das Programm Python 2.7.12 auf den Rechner installiert.

Dann habe ich die überarbeitete Variante in das Programm eingefügt. Aber es passiert nichts. Was mache ich falsch ?

Kommentar von NoHumanBeing ,

Gehe auf der PasteBin-Seite, die ich oben verlinkt habe, oberhalb des Quelltextes auf den "Download"-Button.

Dann wird Dir eine Datei mit dem Namen "knapsack_revised.py" zum Download angeboten. Diese lädst Du herunter.

Dann öffnest Du eine Eingabeaufforderung, wechselst per "cd" (chance directory) in das Verzeichnis, in das Du die Python-Datei gelegt hast.

(Mit dem Befehl "cd Verzeichnis" wechselst Du in das Unterverzeichnis mit dem Namen "Verzeichnis", mit "cd .." wechselst Du in das übergeordnete Verzeichnis. Mit dem Befehl "dir" kannst Du Dir den Inhalt des aktuellen Verzeichnisses ausgeben lassen.)

Dort angekommen gibst Du folgenden Befehl ein.

python knapsack_revised.py

(Oder wie die Datei auch immer genau heißt.)

Dann führt der Python-Interpreter das Programm aus.

Dies setzt voraus, dass sich der Python-Interpreter in Deinem %PATH% (Windows-Umgebungsvariable) befindet. Ich weiß ja nicht, wie Du Python installiert hast, aber wenn es die Variante mit grafischem Installer war (".msi"-Datei), sollte er den %PATH% eigentlich entsprechend angepasst haben.

Kommentar von NoHumanBeing ,

Ich habe gerade gesehen, dass "Add python.exe to $PATH" im Installer standardmäßig nicht aktiviert ist.

Ich würde empfehlen, den Installer noch einmal durchlaufen zu lassen, mit der Option "Change Python 2.7.12" und dann ganz nach unten zu scrollen und die entsprechende Option zu aktivieren (auf "Will be installed on local hard drive" setzen).

Kommentar von KaiRo1976 ,

Es laüft....

Habe es nun hinbekommen. Funktioniert echt super.

Besten Dank nochmal

Kommentar von NoHumanBeing ,

Keine Ursache! War ne nette kleine Programmierübung. :-)

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten