[Doctor_Che]

Задача о рюкзаке.
По идее программа должна вычислять максимальную стоимость набора при ограниченном весе.
Но судя по всему задача выбирает максимальную стоимость по последнему предмету.
Где ошибка?

В приложенном файле исходники.

Исходные данные для работы программы (Исходные данные для работы программы считываются из файла).

Файл: “ DATA.txt”.

3
49
8 22
10 28
14 40

Исходный текст программы.

Код:

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

Const NMax = 100;

type

Thash = array[0..1000] of longint;
TC = array[1..NMax] of longint;
TW = array[0..NMax] of longint;
TT = array[0..NMax,0..NMax] of Integer;
Tbit = array[0..NMax] of byte;

TForm1 = class(TForm)
ListBox1: TListBox;
Button_Save: TButton;
Label_FileNameOut: TLabel;
SaveDialog_Out: TSaveDialog;
procedure FormCreate(Sender: TObject);
procedure Button_SaveClick(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
i,j,k,p:Integer;
N,M:Integer; {kol-vo raznovidnostey elementov i gruzopod'emnost'}
sum:Integer;
b:Boolean;
total:longint; {nabrannaia massa iz elementov}
cost:longint;
max:Integer;
hash : Thash;
C : TC;
W : TW;
T : TT;
bit : Tbit;
kbit : Tbit;
implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
ListBox1.Clear;
AssignFile(input,'DATA.txt');
Reset(input);
readln(N,M);
for i:=1 to N do begin
readln(W[i],C[i]);
bit[i]:=0; { bit vhojdeniia: esli=1, to vhodit, inache net }
kbit[i]:=0; { kol-vo vhojdenii elementa}
hash[C[i]]:=i; { sviazivaem napriamuiu stoimost' s poriadkovim nomerom}
end;
hash[0]:=0;
closefile(input);

T[0,0]:=0;
for j:=1 to M do T[0,j]:=0;
for i:=1 to N do T[i,0]:=0;


{sortiruem dlia uprosheniia poiska}

for j:=1 to N-1 do begin
for i:=1 to N-j do begin
if C[i]>C[i+1] then begin
p:=W[i]; k:=C[i];
W[i]:=W[i+1]; C[i]:=C[i+1];
W[i+1]:=p; C[i+1]:=k;
end;
end;
end;

for k:=1 to N do begin
for i:=1 to N do begin
for j:=1 to M do begin
if j>=W[i] then begin
max:=0;
for p:=1 to k do
if j>=W[p] then
if (T[i-1,j-W[p]]+C[p])>max then max := T[i-1,j-W[p]]+C[p];
if T[i-1,j] >= max then T[i,j]:=T[i-1,j]
else T[i,j]:=max;
end else T[i,j]:=T[i-1,j];
end;
end;
end;


{poisk, ispol'zuia hash}
b:=true;
W[0]:=0;
total:=0;
while b=true do begin
for i:=N downto 1 do begin
if total+W[hash[T[i,M]-T[i-1,M]]] >= M then begin
b:=false;
break;
end else begin
total:=total+W[hash[T[i,M]-T[i-1,M]]];
bit[hash[T[i,M]-T[i-1,M]]]:=1;
inc(kbit[hash[T[i,M]-T[i-1,M]]]);
end;
end;
if b = false then break;
end;


{vivod rezul'tatov}
ListBox1.Items.Append('Исходный набор предметов:');
ListBox1.Items.Append('');
for i:=1 to N do begin
ListBox1.Items.Append('Товар № ' + IntToStr(i));
ListBox1.Items.Append(' вес: =' + IntToStr(W[i]) + ', цена: =' + IntToStr(C[i]));
end;
ListBox1.Items.Append('');
ListBox1.Items.Append('Максимальный вес: ' + IntToStr(M));
ListBox1.Items.Append('');
ListBox1.Items.Append('Результат');
ListBox1.Items.Append('-------------------------------------------------');
total:=0;
cost:=0;
ListBox1.Items.Append('');
k:=0;
ListBox1.Items.Append('Итоговый оптимальный набор:');
ListBox1.Items.Append('');
for i:=1 to N do begin
if bit[i]=1 then begin
ListBox1.Items.Append('Товар № ' + IntToStr(i));
ListBox1.Items.Append(' вес: ' + IntToStr(W[i]) + ', стоимость: ' + IntToStr(C[i]));
ListBox1.Items.Append(' - ' + IntToStr(kbit[i]) + ' шт.');
total:=total+W[i]*kbit[i];
cost:=cost+C[i]*kbit[i];
end;
end;
ListBox1.Items.Append('');
ListBox1.Items.Append('Максимальный вес набора: ' + IntToStr(total));
ListBox1.Items.Append('');
ListBox1.Items.Append('Максимальная цена набора: ' + IntToStr(cost));
end;

procedure TForm1.Button_SaveClick(Sender: TObject);
begin
Form1.Label_FileNameOut.Caption:= 'Out.txt';
Form1.ListBox1.Items.SaveToFile('Out.txt');
end;

end.

Результаты работы программы (результаты работы программы записываются в файл).

Исходный набор предметов:

Товар № 1
вес: =8, цена: =22
Товар № 2
вес: =10, цена: =28
Товар № 3
вес: =14, цена: =40

Максимальный вес: 49

Результат
-------------------------------------------------

Итоговый оптимальный набор:

Товар № 3
вес: 14, стоимость: 40
- 3 шт.

Максимальный вес набора: 42

Максимальная цена набора: 120

Полученный набор имеет не максимальную стоимость, ищите ошибки в программе.