aus mehreren Werten größte Kombination.
hy leute ich habe ein Problem.
Wie kann ich aus mehreren Werten die größtmöglichste Kombination innerhalb eines Wertes herausbekommen. z.B. Ich habe die Zahlen 250, 700 und 900 und möchte die größtmöglichste Werte kleiner als 1000. 900 ist ja hier der Größte Wert, aber 700 + 250 ist hier in Kombination der größte mögliche Wert. Ich habe dazu einfach keine Idee. wäre nett, wenn ihr mir helfen könnet. Mfg Noobinator |
Re: aus mehreren Werten größte Kombination.
Bundeswettbewerb Informatik ;)
Nenene, da komm mal selber drauf^^ |
Re: aus mehreren Werten größte Kombination.
Hi,
hatte ich gerade am Wickel. Schau auch noch mal hier -> Variation Und hier noch mal mein bescheidenes Formelwerk:
Delphi-Quellcode:
Für den Part mit den Wiederholungen war ich dann zu faul, weil ich es nicht brauchte. Sorry
Function Fakultaet(Elemente : Integer) : Int64;
var Counter : Integer; begin Result := 1; For counter := 1 to Elemente do Result := Result * Counter; end; Function Variation(Elemente, Klasse : Integer; Wiederholung : Boolean) : Int64; var Counter : Integer; begin Result := 1; IF Wiederholung then begin // mit Wiederholungen end else begin // ohne Wiederholungen For Counter := Elemente downto Elemente - Klasse + 1 do Result := Result * Counter; end; end; Function Kombination(Elemente, Klasse : Integer; Wiederholung : Boolean) : Int64; begin IF Wiederholung then begin // mit Wiederholungen end else begin // ohne Wiederholungen Result := Trunc(Variation(Elemente, Klasse, False) / Fakultaet(Klasse)); end; end; Gruß oki |
Re: aus mehreren Werten größte Kombination.
o.O ne wasn das?
Ich soll das als Hausaufgabe zu morgen machen. hat unser Lehrer uns letzte Woche als Langwierige Ha aufgegeben, und ich habe das mal wieder aufgeschoben. :wall: Komme einfach nicht auf eine vernünftige Variante :cry: |
Re: aus mehreren Werten größte Kombination.
Zitat:
|
Re: aus mehreren Werten größte Kombination.
Sorry,
hab auch grad gemerkt dass ich da etwas daneben liege :oops: Bis zum Ende lesen erspart Peinlichkeit. gruß oki |
Re: aus mehreren Werten größte Kombination.
Ich würd sagen, da muss man mehr oder weniger alles durchprobieren lassen und dann gucken, was das Beste war.
|
Re: aus mehreren Werten größte Kombination.
Ganz simpler Ansatz:
- alle Zahlen nehmen, die einzeln kleiner als die Gesamtzahl sind - die Menge durchlaufen, von der größten Zahl bis zur kleinsten Zahl - bei jedem Durchlauf prüfen, ob die Zahl noch drauf passt Nach einem Durchlauf hast du eine mögliche Kombination. Jetzt wiederholst du den Durchlauf und lässt jedes Mal die größte Zahl raus, damit die "kleinen" Zahlen, die vorher nicht mehr gepasst haben, zusammen eine größere Zahl ergeben, als die "große" Zahl alleine und somit evtl. eine höheres Gesamtergebniss erzielt wird. |
Re: aus mehreren Werten größte Kombination.
@ ste_ett:
Hm. Kriegt man damit denn auch gesichert die optimale Lösung? Nehmen wir mal die Zahlen 2, 4, 5, 10, Gesamtzahl ist 16. Dann fängt er mit der 10 an, packt die 5 dazu, die 2 und 4 passen dann nicht mehr drauf. Dann lässt er die 10 weg und versucht nur mit den anderen Zahlen. Die beste gefundene Lösung wird 10 + 5 bleiben. 10 + 4 + 2 würde die Gesamtzahl aber erreichen. Hab ich dich nicht verstanden? |
Re: aus mehreren Werten größte Kombination.
Das ist im Endeffekt so etwas wie das Rucksack-Problem, nur etwas einfacher, da in diesem Fall Nutzwert=Gewicht. Such mal nach "Rucksack Problem".
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 05:37 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz