aus mehreren Werten größte Kombination.

[Noobinator]

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

[inherited]

Bundeswettbewerb Informatik
Nenene, da komm mal selber drauf^^

[oki]

Hi,

hatte ich gerade am Wickel. Schau auch noch mal hier -> Variation

Und hier noch mal mein bescheidenes Formelwerk:

Delphi-Quellcode:

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;

Für den Part mit den Wiederholungen war ich dann zu faul, weil ich es nicht brauchte. Sorry

Gruß oki

[Noobinator]

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.
Komme einfach nicht auf eine vernünftige Variante

[Noobinator]

Zitat von oki:

Hi,

hatte ich gerade am Wickel. Schau auch noch mal hier -> Variation

Und hier noch mal mein bescheidenes Formelwerk:

...

Für den Part mit den Wiederholungen war ich dann zu faul, weil ich es nicht brauchte. Sorry

Gruß oki

Danke erstmal, aber inwiefern hilft mir das Bei meinem Problem?

[oki]

Sorry,

hab auch grad gemerkt dass ich da etwas daneben liege
Bis zum Ende lesen erspart Peinlichkeit.

gruß oki

[Cöster]

Ich würd sagen, da muss man mehr oder weniger alles durchprobieren lassen und dann gucken, was das Beste war.

[ste_ett]

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.

[Cöster]

@ 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?

[3_of_8]

Das ist im Endeffekt so etwas wie das Rucksack-Problem, nur etwas einfacher, da in diesem Fall Nutzwert=Gewicht. Such mal nach "Rucksack Problem".