01背包 pascal（有人能解嘛？要自己编的，今天！）

01背包问题太过经典,我换一种方式描述.我有一个无穷大的硬盘(好贵的噢),然后我喜欢看很多经典的电影,但是下载起来很费时间.于是我决定只下载其中的一部分.同时只能下载一部电影,每部电影有一个确定的下载时间,我要在有限时间内下载容量最大的电影,因为我的硬盘无限大,嘿嘿.



Input多组数据,每组由2个数字在第一行,M(<=100) 和 N(<=600). M 表示我可以选择的电影有多少部N表示时间限制,接下来的M行表示每部电影的下载时间和容量.2个0表示数据结束,不用处理.

Output输出我在有限时间里最多可以下载多大的电影.

Sample Input2 60
50 500
55 600
3 60
10 400
25 500
30 600
0 0

Sample Output600
1100

自创回溯+穷举+动态规划 呵呵 绝对最优解

program greed;
var w,p:array[1..100]of integer;
res,temp:array[1..100]of 0..1;
weight,n,x,max:integer;
procedure search(sy,k,now:integer);
var i,j:integer;
begin
if ((k=0)and(sy=0)) then
begin
if now>max then
for i:=1 to n do begin res[i]:=temp[i];max:=now;end;
exit;
end;
for i:=k downto 1 do
if ((sy>=w[i])and(temp[i]=0)) then
begin
temp[i]:=1;now:=now+p[i];sy:=sy-w[i];
search(sy,k-1,now);
temp[i]:=0;now:=now-p[i];sy:=sy+w[i];
end
else search(sy,k-1,now);
end;
begin
read(weight,n);
for x:=1 to n do read(w[x],p[x]);
max:=0;
for x:=n downto 1 do
begin
fillchar(temp,n,0);
search(weight,x,0);
end;
writeln;
for x:=1 to n do write(res[x]:3);
writeln;
writeln(max);
end.

const maxm=200;maxn=30; type ar=array[1..maxn] of integer; var m,n,j,i:integer; c,w:ar; f:array[0..maxn,0..maxm] of integer; function max(x,y:integer):integer; begin if x>y then max:=x else max:=y; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); for i:=1 to m do f(0,i):=0; for i:=1 to n do f(i,0):=0; for i:=1 to n do for j:=1 to m do begin if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])｛如果当前背包可以装入背包I且装入后最大则装入I｝ else f[i,j]:=f[i-1,j]; end; writeln(f[n,m]);

proggram bb_Zo;

type ar=array[0..1000] of integer; arr=array[0..100,0..100] of integer; var a,w,c:ar; n,v,i,j,max:longint;

procedure bbzo; var f:arr; begin readln(n,v); for i:=1 to n do read(w[i]); for i:=1 to n do read(c[i]); for i:=1 to n do for j:=1 to v do begin f[i,j]:=f[i-1,j]; if (j>=w[i])and(f[i,j]<f[i-1,j-w[i]]+c[i]) then f[i,j]:=f[i-1,j-w[i]]+c[i]; end; write(f[n,v]); end;

procedure bbzo_2; var f:ar; begin readln(n,v); fillchar(f,sizeof(f),0); for i:=1 to n do read(w[i]); for i:=1 to n do read(c[i]); for i:=1 to n do for j:=v downto w[i] do {注意这一行，把Downto改成To基本就是完全背包了} if f[j]<c[i]+f[j-w[i]] then f[j]:=c[i]+f[j-w[i]]; write(f[v]); end;

begin

// bbzo;

bbzo_2;

end.

有两个过程，bbzo是2维零一背包，bbzo_2是改版之后的，用的是一维数组

如你所见，主程序调用的是1维的那个

program medic; var i,j,t,m:integer; s,v:array[1..100]of integer; o:array[1..1000]of integer; begin readln(m,t); fillchar(o,sizeof(o),0); for i:=1 to m do begin readln(s[i],v[i]); for j:=t downto s[i] do if(o[j-s[i]]+v[i]>o[j]) then o[j]:=o[j-s[i]]+v[i]; end; writeln(o[t]); end.

数据范围自己看着改吧；

o【i】是状态记录；

s【i】价值，即下载空间；

v[i] 经典背包空间，即下载时间；

测试数据全过；