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