Алгоритм рюкзака на Delphi
var a,b:array[1..100] of integer;
n:byte; sum:integer;
f:boolean;
i,j,k,h,s,m,z:integer;
otvet: string;
begin
//Ввод данных
n := StrTointDef(Edit1.Text, 0);
if n = 0 then
begin
ShowMessage('Не задано количество предметов');
exit
end;
with StringGrid1 do
for i := 1 to n do
a[i] := StrTointDef(Cells[1,i], 0);
sum := StrTointDef(Edit2.Text, 0);
if sum = 0 then
begin
ShowMessage('Не задан максимальный вес ранца');
exit
end;
otvet := 'В ранец необходимо поместить предметы: ';
For I := N Downto 1 Do
Begin
B[1] := I;
H := 1;
K := Sum - A[I];
F := False;
Repeat
For J := B[H]-1 Downto 1 Do
Begin
If A[J] <= K Then
Begin
Inc(H);
B[H] := J;
Dec(K, A[J]);
End;
If K = 0 Then
Begin
For M := 1 to H Do otvet := otvet + IntToStr(A[B[M]]) + ' ';
Inc(K, A[B[H]]);
Dec(H);
End;
End;
F := True;
For M := H Downto 2 Do
Begin
If B[M] <> H-M+1 Then
Begin
F := False;
Dec(B[M]);
H := M;
K := Sum;
For Z := 1 to H Do
Dec(K, A[B[Z]]);
Break;
End;
End;
Until F;
End;
memo1.Lines.Add(otvet)