Java Addition mögliche Kombinationen von Summanden aus Liste um spezifische Zahl als Summe zu erhalten?
Hey,
folgende Aufgabe ist zu lösen:
class Scale {
static List<Integer> getMasses(Integer weight, List<Integer> allMasses) {
// You need to implement this method.
// You can also add attributes to the class and add new methods or functions
}
}
Given is a List<Integer> which includes the calibrated masses of the balance.
Your Object weighs only 145 grams.
Your function should return an List<Integer> with all needed masses to weigh the Object:
[1, 16, 128]
Your algorithm should work with lighter and heavier objects as well.
Wichtig! Note that you can use every single mass only once!
Im ersten Durchlauf lautet die Funktion:
getMasses(145, [1, 2, 4, 8, 16, 32, 64, 128]);
Das Ergebnis (wie schon erwähnt) soll lauten:
[1, 16, 128]
Da diese 3 Summanden die Summe 145 ergeben.
Freue mich auf eine Anwort :)
MfG
3 Antworten
Suche die nächst kleinere Zahl nach der gesuchten Zahl (128) und ziehe diese ab
145 - 128 = 17
Suche wieder die nächst kleinere Zahl (16)
17-16 = 1
Das gleiche bringt dich zur 1.
1-1 = 0 = geschafft
Ist einfach das normale binär System
Vielleicht einfach systematisch alle kombinationen durchprobieren?
du willst 145 rauskriegen.
sei a=145.
du suchst dir die größte zahl, die <=a=145 ist aus der liste raus und testest mit der weiter.
vermuten wir dass 128 die erste zahl ist.
dann gucken wir uns alle zahlen beginnend bei er größten zahl, die <= a:=145-128=17 ist, an.
die nächste passende zahl ist 16.
ziehen wir also wieder ab:
a=17-16=1
nun betrachten wir alle zahlen aus der liste mit <=1
passenderweise ist die erstbeste zahl die 1 und wir sind fertig. denn nun wird a auf 1-1=0 gesetzt, was das ende bedeutet.
natürlich müssen wir uns entlang des wegs die als richtig erkannten zahlen merken.
was aber auch passieren kann:
wir sind bspw. bei a=3 angekommen, aber in derliste sind keine zahlen <=3 drin.
dann haben wir ein problem, denn mit den bisher genutzten zahlen finden wir keine weitere zahl sodass sich alles auf 145 aufaddiert.
demnach war zumindest diese kombination falsch.
anderes beispiel:
suchen wir a=55.
wir suchen die nächstkleinere zahl der liste:
33 und merken die uns.
setzen a=55-32=23
nächstkleinere zahl gleich 16
setze a=23-16=7
nächstkleinere zahl 4
a=7-4=3 setzen
nächstkleiner: 2
a=3-2=1
nächstkleiner 1
a=1-1=0
wir sind fertig.
lösung:1,2,4,16
mal noch ein beispiel wo es unsere erste vermutung nicht tut:
bei a=0 funktioniert es offensichtlich nicht (lösung leere integerlsite oder so), bei negativen zahlen sowieso nicht,
alles was größer als 255 (=summe aller zahlen in der liste) ist funktioniert in deinem beispiel auch nicht.
je nahc aufbau deiner liste kann es auch sein dass manche zahlen gar nicht möglich sind bzw. nur mit umwegen:
(100,[1,55,88])
es dürfte recht offensichtlich klar sein dass sich 100 nicht als eine kobination der zahlen darstellen lässt.
aber versuchen wir es doch mal wie oben:
a=100 zu beginn
nächstkleiner: 88
also a=100-88=12
nächstkleiner: 1
also a=12-11
nun haben wir ein problem:
die 1 haben wir shcon benutzt, dürfen wir also nicht nochmal.
und haben aber noch 11 veerbleibend, die wir nicht durch eine summe von kleineren zahlen darstellen können.
sobald in einem schritt im algorithmus zu a keine noch nicht benutzte zahl existiert, die <=a ist, und aber a>0 zu dem zeitpunkt ist, muss abgebrochen werden, wiel unlösbar.
gleiches gilt falls aus welchem grund auch immer ein negatives a irgendwo rauskommen sollte.
und vor dem ganzen tratra sollte zuerst geprüft werden ob überhaupt
0<a<summe der listenelemente ist
denn alles ausserhalb dieses intervalls lässt sich eh nicht darstellen.
ansonsten musst du halt nebenher eine integerliste aufbauen, die mit jedem gefundenen element erweitert wird.
Überlege doch erst einmal selbst, wie du verschiedene solcher Aufgaben schrittweise lösen würdest. Z.B. für die Summen 5, 76 und 12 (o.a.). Trenne dich von der Programmiersprache, die ist hierfür erst einmal unwichtig.