//www.algorytm.org
//Tomasz Lubiński (c)2001
unit Dynamic;

interface

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

type
  TForm1 = class(TForm)
    GroupBox1: TGroupBox;
    Edit1: TEdit;
    Label1: TLabel;
    Edit2: TEdit;
    Label2: TLabel;
    ListBox1: TListBox;
    Button1: TButton;
    Button2: TButton;
    Label3: TLabel;
    Label4: TLabel;
    Edit3: TEdit;
    Edit4: TEdit;
    ListBox2: TListBox;
    Label8: TLabel;
    procedure Generuj(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  b,n: Integer;
  a,c,rozw: Array of Integer;
  f,x: Array of Array of Integer;
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Generuj(Sender: TObject);
var i,p,w:Integer;
begin
b:=StrToInt(Edit1.Text);
n:=StrToInt(Edit2.Text);
p:=StrToInt(Edit4.Text);
w:=StrToInt(Edit3.Text);
SetLength(a,n+1);  SetLength(c,n+1);
ListBox1.Clear;
Randomize;
 for i:=1 to n do
  begin
  a[i]:=Random(w)+1;
  c[i]:=Random(p)+1;
  end;
ListBox1.Items.Add('typ    |   ciężar   |   pojemnosc ');
ListBox1.Items.Add('--------------------------------------------------');
 for i:=1 to n do
  ListBox1.Items.Add(IntToStr(i)+'              '+IntToStr(a[i])+'                '+IntToStr(c[i]));
end;

procedure TForm1.Button2Click(Sender: TObject);
var j,l:Integer;
begin
SetLength(rozw, n+1);
SetLength(f,n+1,b+1);  SetLength(x,n+1,b+1);
for l:=0 to b do
 begin
 f[1,l]:=c[1]*Trunc(l/a[1]);
 if f[1,l]=0 then x[1,l]:=0 Else x[1,l]:=1;
 end;
for j:=2 to n do
 for l:=0 to b do
  begin
   if l-a[j]<0 then f[j,l]:=f[j-1,l]
    else if f[j-1,l]>f[j,l-a[j]]+c[j] then f[j,l]:=f[j-1,l]
     else f[j,l]:=f[j,l-a[j]]+c[j];
   if l-a[j]<0 then x[j,l]:=x[j-1,l]
    else if f[j-1,l]>f[j,l-a[j]]+c[j] then x[j,l]:=x[j-1,l]
     else x[j,l]:=j;
  end;
j:=b;
repeat
Inc(rozw[x[n,j]]);  //wyznaczenie ostatecznego rozwiazania
j:=j-a[x[n,j]];
until (j<=0) or (a[x[n,j]]=0);
ListBox2.Clear;               //wypisanie ostatecznego rozwiązania
ListBox2.Items.Add('typ     |    ilosc   ');
 for j:=1 to n do
  ListBox2.Items.Add(IntToStr(j)+'              '+IntToStr(rozw[j]));
Finalize(rozw);
Finalize(f); Finalize(x);
end;

end.