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?

... komplette Frage anzeigen

1 Antwort

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.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von NoHumanBeing
21.11.2016, 19:07

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

0

Was möchtest Du wissen?