浙江友谊阀门有限公司:背包问题

program beibao;

　　const
　　m=150;
　　n=7;
　　var
　　xu:integer;
　　i,j:integer;
　　goods:array[1..n,0..2] of integer;
　　ok:array[1..n,1..2] of real;

　　procedure init;
　　var
　　i:integer;
　　begin
　　xu:=m;
　　for i:=1 to n do
　　begin
　　write('Enter the price and weight of the ',i,'th goods:');
　　goods[i,0]:=i;
　　read(goods[i,1],goods[i,2]);
　　readln;
　　ok[i,1]:=0; ok[i,2]:=0;
　　end;
　　end;

　　procedure make;
　　var
　　bi:array[1..n] of real;
　　i,j:integer;
　　temp1,temp2,temp0:integer;
　　begin
　　for i:=1 to n do
　　bi[i]:=goods[i,1]/goods[i,2];
　　for i:=1 to n-1 do
　　for j:=i+1 to n do
　　begin
　　if bi[i]<bi[j] then begin
　　temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
　　goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
　　goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
　　end;
　　end;
　　end;

　　begin
　　init;
　　make;
　　for i:=1 to 7 do
　　begin
　　if goods[i,2]>xu then break;
　　ok[i,1]:=goods[i,0]; ok[i,2]:=1;
　　xu:=xu-goods[i,2];
　　end;
　　j:=i;
　　if i<=n then
　　begin
　　ok[i,1]:=goods[i,0];
　　ok[i,2]:=xu/goods[i,2];
　　end;
　　for i:=1 to j do
　　writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
　　end.

用贪心做！01背包用DP