Größtmögliche Anzahl an Kombinationen ohne Zurücklegen
-
Hallo allerseits,
ich habe eine Zahlenmenge, und möchte diese auf Möglichkeiten zur Bildung einer bestimmten Summe untersuchen.
Beispiel: 1,1,1,2,2,3,4. Untersuchen auf Summe = 3. Diese kann ich machen mit 1+1+1 und 3 oder 1+2 und 1+2 und 3. Dh mein Ergebnis von maximal möglichen Kombinationen wäre hier das letzte: 3.Aber wie komme ich auf eine Formel/Algorithmus, den ich auf die Zahlenmenge loslassen kann?
Danke und Gruß
-
Man kommt durch nachdenken drauf!
Ausserdem: Dein Problem ist unklar formuliert: 1,1,1,2,2 ist keine Menge. Wenn du aber jede 1 und jede 2 als verschieden betrachtest, so gibt es mehr Moeglichkeiten als deine 3. Btw. die groesstmoegliche Anzahl ohne zuruecklegen ist n! (Fakultaet), wenn deine Menge n Elemente hat.
-
Ja aber es klappt einfach nicht. Habe mir schon viele viele Beispiele aufgeschrieben, aber ich schaffs einfach nicht die Struktur dahinter zu erkennen.
Sorry wenn ich unklar formuliert habe. Ja, die Zahlen zB 1,1,1 sollen als verschieden betrachtet werden.
Trotzdem erschließt sich für mein Beispiel nur die Lösung '1+2 und 1+2 und 3', um jeweils mit den enthaltenen Elementen eine Summe von 3 zu bilden.n! würde ich nutzen, wenn ich alle möglichen Anordnungen aller meiner vorhandenen Zahlen haben möchte. Aber das ist ja nicht mein Ziel. Ich möchte nur im Hinblick auf eine bestimmte Summe hin untersuchen...
-
Also ich würd irgendwie zuerst alle größer als das Ergebnis rausschmeißen. Dann würde ich die größte übriggebliebene zahl nehmen, die von dem ergebnis abziehen und dann steht man mit dieser Differenz wieder am Eingangsproblem, hat also die Rekursion praktisch schon vor Augen. Und halt abbrechen, falls es keine Kombination mehr gibt...
-
Das könnte in die richtige Richtugn gehen.
Nur wie markiere ich die Zahlen, die ich schon 'verwertet' habe? Wenn ich zB auf Summe=5 teste, dann nehm ich von oben angefangen die 4+1. Und wenn es mehrere 4en gibt, dann darf die schon verwendete 1 ja nicht nochmal mitkombiniert werden. Irgendwie müsste ich diese dann markieren können...
-
Sortiere die Liste vor und betrachte nur Zahlen die unter einem gewissen Index auftauchen (Wenn die größten Zahlen hinten sind). Jedes mal wenn du eine Zahl mit einem gewissen Index auswählst, werden dann ja nur noch weitere Zahlen mit niedrigerem Index benutzt.
-
Ich schreibe deine Menge mal anders auf: 1a,1b,1c,2a,2b,3,4. Daraus folgt 1a+2a = 3, 1a+2b = 3, 1b+2a = 3, 1b+2b = 3, 1c+2a = 3, 1c+2b = 3 und 3 selbst. Das sind 7 (sieben) Moeglichkeiten.
erschließt sich für mein Beispiel
Mir erschliesst sich garnichts, wahrscheinlich weil du das Problem nicht genau beschrieben hast.
-
knivil schrieb:
Ich schreibe deine Menge mal anders auf: 1a,1b,1c,2a,2b,3,4. Daraus folgt 1a+2a = 3, 1a+2b = 3, 1b+2a = 3, 1b+2b = 3, 1c+2a = 3, 1c+2b = 3 und 3 selbst. Das sind 7 (sieben) Moeglichkeiten.
die 3 fällt weg, weil keine 0 enthalten ist, mit der man auf die summe 3 kommen kann. wieso hängst du buchstaben an die zahlen? nur weil elemnte von mengen einzigartig sein müssen? sowas verwirrt doch mehr, als dass es hilft.
-
Ne, weil die erste 1 sich von der zweiten unterscheiden soll (laut Problembeschreibung). Aber wenn ich jetzt sechs mal 1+2 aufschreibe, kapierts keiner, was ich meine. Ausserdem habe ich noch 1a+1b+1c = 3 vergessen, sind also 8 Moeglichkeiten. Das mit der 3 habe ich aus einem Beitrag vorher uebernommen.
-
knivil schrieb:
Aber wenn ich jetzt sechs mal 1+2 aufschreibe, kapierts keiner, was ich meine. Ausserdem habe ich noch 1a+1b+1c = 3 vergessen, sind also 8 Moeglichkeiten.
das kapiert man doch. jede 1 mit der ersten 2 und dann das ganze nochmal für die andere 2, plus die drei einsen macht 7 möglichkeiten.
-
Im zweiten Post hab ich es probiert, leider hat es nicht geklappt.