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

[Noobinator]

Zitat:

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 :oops:
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".

[shmia]

Es handelt sich um das bekannte Rucksackproblem:
http://de.wikipedia.org/wiki/Rucksackproblem
Ich glaube nicht, dass wir hier noch weiterdiskutieren; du weisst jetzt nach was du suchen musst.

[Cöster]

Vom Code her ist das vielleicht leichter zu lösen als das Rucksackproblem. Der Grund dafür ist aber, dass man hier nen Brute Force drauf loslassen MUSS (oder?). Beim Rucksackproblem ist das nicht der Fall. Deswegen ist der Code auch anders als beim Rucksackproblem, es sei denn das Rucksackproblem wird auch mit Brute Force gelöst (was nicht ratsam ist).

[3_of_8]

Naja, nicht ganz.

Beim Rucksackproblem sieht das in etwa so aus:

Eine Menge M besteht aus Vektoren v(1)...v(o) mit v(i)=(m(i), n(i)) für alle 1<=i<=o.

Was man haben will, ist der größte Wert n mit n=a(i)*n(i) für alle 1<=i<=o, wobei m(max)>=a(i)*m(i).

a(i) element {0;1}, a(i)=0 bedeutet "Objekt nicht in Rucksack", a(i)=1 bedeutet "Objekt im Rucksack".

m(i) ist das Gewicht des Objektes i, m(max) ist das Maximalgewicht.

n(i) ist der Nutzwert des Objektes i, n ist der Gesamtnutzwert aller Objekte im Rucksack.

Die Koeffizienten a(1)...a(o) und die größte Zahl n sind gesucht.


Dieses Problem ist etwas einfacher:

Hier ist aus einer Menge ganzer Zahlen z(1)...z(o) die größte Summe n=a(i)*n(i) mit 1<=i<=o gesucht mit n<n(max).

Hier hat man also statt Gewichts- und Nutzwert nur einen Wert.

Gesucht ist hier die größte Zahl n.

[Cöster]

Sicher hat das Problem Parallelen mit dem Rucksackproblem, ließe sich sogar mit einem Algorithmus für das Rucksackproblem lösen. Das ist aber überhaupt nicht notwendig und würde viel zu lange dauern, da unnötige Rechnungen vorgenommen würden. Ein guter (= nicht Brute Force) Algorithmus für das Rucksackproblem hätte ziemlich wenig Ähnlichkeiten mit einem guten Algorithmus für dieses Problem, auch wenn das Problem auf den ersten Blick fast gleich aussieht.

[3_of_8]

Ich bezog mich auf shmias Aussage und habe sie widerlegt.

Ich sage ja: Es ist NICHT das Rucksackproblem bzw. man könnte es als Sonderfall des Rucksackproblems sehen, aber schon ein sehr besonderer. ;)

Prinzipiell würde ich das ganze so machen:

Delphi-Quellcode:

function FindCombination(a: TIntegerDynArray; maxValue: Integer): Integer;
var I, J, value, max: Integer;
begin
  I:=0;
  max:=0;
  while I<length(a) do
  begin
    if a[I]=maxValue then
    begin
      result:=a[I];
      exit;
    end else if a[I]<maxValue then
    begin
      value:=a[I];
      for J:=Succ(I) to high(a) do
        if value+a[J]<maxValue then inc(value, a[J]);
      if value>max then max:=value;
    end;
  inc(I);
  end;
  result:=max;
end;

EDIT: Dummer Fehler...

[Noobinator]

Danke leute, aber ich habe das Inzwischen selbstständig ohne Wiki und co gelöst...
hat auch nur 1h gedauert :wink:

danke hier kann das geclosed werden.

[3_of_8]

1. Dann poste doch bitte deine Lösung
2. Wozu schließen?

[Cöster]

Zitat:

Zitat von 3_of_8

Delphi-Quellcode:

function FindCombination(a: TIntegerDynArray; maxValue: Integer): Integer;
var I, J, value, max: Integer;
begin
  I:=0;
  max:=0;
  while I<length(a) do
  begin
    if a[I]=maxValue then
    begin
      result:=a[I];
      exit;
    end else if a[I]&lt;maxValue then
    begin
      value:=a[I];
      for J:=Succ(I) to high(a) do
        if a[J]&lt;maxValue then inc(value, a[J]);
      if value>max then max:=value;
    end;
  inc(I);
  end;
  result:=max;
end;

So wird das nicht funktionieren. Ich überleg mir auch mal eben was.

[3_of_8]

Warum nicht?

EDIT: Aaah, ja, klar... Mist...

[marabu]

Hallo,

die Optimierung von Teilsummen (Zuschnittsproblem, Rucksackproblem) ist einfach, aber zeitaufwendig. Aus didaktischen Gründen habe ich die Teilsummenberechnung ausgeklammert. Integriert man sie in die Hauptfunktion, so kann die Zahl der Schleifendurchläufe durch ein zusätzliches Abbruchkriterium (Result > iLimit) optimiert werden, da keine weiteren Summanden mehr berücksichtigt werden müssen. Das Ergebnis für BestPartialSum([250,700,900], 1000) ist 3 - die Bitmaske für die Summanden einer optimalen Teilsumme. Code für einen maximal 32 stelligen Summanden-Vektor:

Delphi-Quellcode:

function PartialSum(const v: array of Cardinal; index: Cardinal): Int64;
var
  i: Integer ;
begin
  Result := 0;
  for i := 0 to 31 do
  begin
    if index = 0 then
      Exit else
    if Odd(index) then
      Inc(Result, v[i]);
    index := index shr 1;
  end;
end;

function BestPartialSum(const v: array of Cardinal; iLimit: Int64): Cardinal;
var
  i, iBest: Cardinal;
  ps, psBest: Int64;
begin
  psBest := 0;
  for i := 1 to Pred(1 shl Length(v)) do
  begin
    ps := PartialSum(v, i);
    if ps = iLimit then
    begin
      Result := i;
      Exit;
    end else
    if (ps < iLimit) and (ps > psBest) then
    begin
      iBest := i;
      psBest := ps;
    end;
  end;
  Result := iBest;
end;

Getippt und nicht lange getestet.

Grüße vom marabu

[Cöster]

Hier mal eine zweite (rekursive) Lösung:

Delphi-Quellcode:

TIntArray = array of Integer;

TCombi = record
  Factors: array of Boolean;
  Value: Integer;
end;

{...}

function TForm1.GetCombi(const Ints: TIntArray; Combi: TCombi; I, Limit: Integer): TCombi;
var
  Combi2: TCombi;
begin
  Combi.Factors := Copy(Combi.Factors);
  if Combi.Factors[I] then
  begin
    Combi.Factors[I] := False;
    Dec(Combi.Value, Ints[I]);
  end;
  if I < High(Ints) then
  begin
    Combi2 := GetCombi(Ints, Combi, I + 1, Limit);
    Combi.Factors[I] := True;
    Inc(Combi.Value, Ints[I]);
    Result := GetCombi(Ints, Combi, I + 1, Limit);
    if Result.Value < Combi2.Value then
      Result := Combi2;
  end
  else
  begin
    Combi.Factors[I] := True;
    Inc(Combi.Value, Ints[I]);
    if Combi.Value > Limit then
    begin
      Combi.Factors[I] := False;
      Dec(Combi.Value, Ints[I]);
      if Combi.Value > Limit then
        Combi.Value := -1;
    end;
    Result := Combi;
  end;
end;

Zur Erklärung der Parameter:
Ints sind die Zahlen, aus denen die Kombination gefunden werden soll.
Combi speichert, welche Indizes aus Ints in der Kombination vorhanden sind und den Gesamtwert.
I ist der Index im Array von Combi, die geändert wird.
Limit ist die Obergrenze.

Wenn jemand Optimierungstipps hat, würde ich sie gerne hören.