Gewichtaufteilung [Yoni's Riddles 7/15]

Freizeit & Hobby Rätsel
#1

Du arbeitest in einem Postamt. Deine Aufgabe besteht darin, das Porto für Pakete aufgrund deren Gewicht (gerundet auf ganze Kilogramm) zu berechnen.
Wegen der Kürzungen im Budget der Wägeabteilung, musst du die Pakete selbst abwiegen. Durch Postamtsvorschriften hast du eine Balkenwaage mit zwei Platten (eine wie sie für juristische Logos üblich ist) sowie vier kalibrierte Gewichte zur Verfügung.
Glücklicherweise nimmt dein Postamt nur Pakete bis 40 kg an, sodass du Kunden mit solchen Paketen zu einem anderen Amt schicken kannst ohne den Preis selbst berechnen zu müssen.
Welche vier Gewichte solltest du haben, um den Preis für alle Pakete ermitteln zu können die du annehmen musst?

Ich kenne die Lösung nicht, ich denke aber, dass hier ein mehrfaches Subset-Sum Problem vorliegt. Dieses ist bekannt dafür NP-Vollständig zu sein.
Außer „probieren“ sollte es also keine Lösungsmöglichkeit geben (insbesondere keine konstruktive). Ich lasse mich aber gerne eines Besseren belehren, die NP-Vollständigkeit ist nur eine Vermutung von mir.

Im PS steht ein Tipp von mir (Teilspoiler?).

MfG
B3ret

PS: Ich nehme an, dass man auch Gewichte gemeinsam mit dem Paket auf dieselbe Schale legen muss um alle 40 Massen abzubilden. Nach dieser Einsicht sollte es nur noch ums „intelligente probieren“ gehen.

#2

Lösung
Guten Morgen,

Welche vier Gewichte solltest du haben, um den Preis für alle
Pakete ermitteln zu können die du annehmen musst?

das Rätsel gab es hier schon mal, wenn ich mich recht erinnere. Die Lösung ist folgende:

Als Gewichte nehme ich die Potenzen von 3: 1, 3, 9, 27
Mit diesen Gewichten lässt sich in einer Art Stellenwertsystem (mit den Ziffern 1, 0 und -1) jedes Gewicht bis 40 darstellen (dabei entspricht „-1“ dem Platzieren des Gewichts auf der anderen Seite der Waage, also dort, wo auch das Paket liegt):

 1 = +1
 2 = +3 -1
 3 = +3
 4 = +3 +1
25 = +27 -3 +1
26 = +27 -1
27 = +27
40 = +27 +9 +3 +1

Andreas

#3

Aber wie stelle ich fest, ob das Paket 1,4 (1) oder 1,6 (2) kg wiegt.
Es sei, es wird nur aufgerundet.
Oder habe ich hier einen Denkfehler ?

cu

#4

Es sei, es wird nur aufgerundet.
Oder habe ich hier einen Denkfehler ?

Nein, hast du nicht. Falls kaufmännisch gerundet werden soll, haben wir ein Problem. Zumindest können wir bestimmen, zwischen welchen Schranken das Gewicht liegt.