aus mehreren Werten größte Kombination.

[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