unit1.~pas

在0 / 1背包问题中

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Bag;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  x:array of boolean;
  p,w:array of integer;
  pw,pw1:array of real;
  c:integer;
  weight:real;
const
  n=3;

implementation

{$R *.dfm}
uses math;

procedure TForm1.Bag;
var
  max:real;
  i,j,t:integer;
  str:string;
begin
//随机生成实验数据
setlength(p,n);
setlength(w,n);
setlength(pw,n);
setlength(pw1,n);
setlength(x,n);
for i:=0 to n-1 do
begin
p[i]:=trunc(random*30)+1;
w[i]:=round(random*10)+1;
pw[i]:=p[i]/w[i];
pw1[i]:=pw[i];
x[i]:=false;
end;
weight:=0;
c:=trunc(random*30)+1;
//c:=random(30);
//输出实验数据
memo1.Lines.Add('共有'+inttostr(n)+'件物品');
memo1.Lines.Add('各物品价值为：');
str:='';
for i:=0 to n-1 do
begin
str:=str+inttostr(p[i])+' '+' '+' ';
end;
memo1.Lines.Add(str);
str:='';
memo1.Lines.Add('各物品重量为：');
for i:=0 to n-1 do
begin
str:=str+inttostr(w[i])+' '+' '+' ';
end;
memo1.Lines.Add(str);
str:='';
memo1.Lines.Add('价格重量比为（乘以十）：');
for i:=0 to n-1 do
begin
str:=str+inttostr(round(10*pw[i]))+' '+' '+' ';
end;
memo1.Lines.Add(str);
str:='';
memo1.Lines.Add('规定总重量为：');
memo1.Lines.Add(inttostr(c)+' '+' '+' ');
//背包问题
t:=0;
for i:=0 to n-1 do
begin
max:=0;
for j:=0 to n-1 do
begin
if (max<pw1[j]) then
begin
max:=pw1[j];
t:=j;
end;
end;
pw1[t]:=0;
if ((weight+w[t])<=c) then
begin
x[t]:=true;
weight:=weight+w[t];
end;
end;
//输出实验结果
memo1.Lines.Add('物品装入背包情况：');
for i:=0 to n-1 do
begin
if(x[i]) then
memo1.Lines.Add('第'+inttostr(i+1)+'种物品装入背包；')
else
memo1.Lines.Add('第'+inttostr(i+1)+'种物品不装入背包；')
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
memo1.Clear;
Bag;
end;

end.