end; begin
assign(input,'Pack.in'); reset(input);
assign(output,'Pack.out'); rewrite(output); main;
close(input); close(output); end. ............ 4、混合背包
program BlendPack;//混合背包 const
maxv=20000; maxn=3000; var
f:array[0..maxv]of longint;
c,w,n,kind:array[1..maxn]of longint; num,v:longint;
procedure makeobject; var
i,k,num2:longint; begin
num2:=num;
for i:=1 to num do if kind=3 then begin kind:=1;
if c*n>v then n:=v div c; k:=2;
while k*2-1<=n do//2进制思想 begin
inc(num2);
c[num2]:=c*k;w[num2]:=w*k; kind[num2]:=1; k:=k*2; end; k:=n-k+1;
if k>0 then //补足n begin
inc(num2);
c[num2]:=c*k;w[num2]:=w*k;
kind[num2]:=1; end; end;
num:=num2; //物品数更新 end;
procedure main; var
i,j,max:longint; begin
readln(num,v); for i:=1 to num do
//标记kind，1为01背包物品，2为完全背包物品，3为多重背包物品 begin
read(kind,c,w);
if kind=3 then read(n); end;
makeobject;//制造倍数物品 for i:=0 to v do f:=0; for i:=1 to num do
if kind=1 then //01背包 begin
for j:=v downto 0 do if c+j<=v then
if w+f[j]>f[c+j] then f[c+j]:=w+f[j];//状态转移方程 end else
begin//完全背包 for j:=0 to v do if c+j<=v then
if w+f[j]>f[c+j] then f[c+j]:=w+f[j];//状态转移方程 end; max:=f[0];
for i:=1 to v do if f>max then max:=f; writeln(max); end; begin
assign(input,'pack.in'); reset(input);
assign(output,'pack.out'); rewrite(output); main;
close(input); close(output); end.
.................. 5、二维背包
program 2DimensionPack;//二维背包 const
maxv=1000; maxn=30; var
f:array[0..maxv,0..maxv]of longint; a,b,w:array[1..maxn]of longint; n,v,u:longint; procedure main; var
i,j,k,max:longint; begin
readln(n,v,u);
for i:=1 to n do read(a,b,w); for i:=0 to v do
for j:=0 to u do f[i,j]:=0; for i:=1 to n do begin
for j:=v downto 0 do for k:=u downto 0 do
if (a+j<=v)and(b+k<=u) then
if f[j,k]+w>f[j+a,k+b] then f[j+a,k+b]:=f[j,k]+w;//状态转移方程 end;
max:=f[0,0]; for i:=0 to v do for j:=0 to u do
if f[i,j]>max then max:=f[i,j]; writeln(max); end; begin
assign(input,'Pack.in'); reset(input);
assign(output,'Pack.out'); rewrite(output); main;
close(input); close(output); end.
........... 6、分组背包
program GroupingPack;//分组背包 const
maxv=20000; maxn=3000; var
f:array[0..maxv]of longint; w,c:array[1..maxn]of longint; n,v:longint; procedure main; var
i,j,max,x,k,nk:longint; begin
readln(n,v,k);
for i:=0 to v do f:=0;
for i:=1 to k do//以组为阶段 begin
read(nk);//组的物品总数
for x:=1 to nk do read(c[x],w[x]);//第I组的物品 for j:=v downto 0 do
for x:=1 to nk do //注意外层循环是v..0，保证同组物品不会同时用 if c[x]+j<=v then
if w[x]+f[j]>f[c[x]+j] then f[c[x]+j]:=w[x]+f[j];//状态转移方程 end;
max:=f[0];
for i:=1 to v do if f>max then max:=f; writeln(max); end; begin
assign(input,'pack.in'); reset(input);
assign(output,'pack.out'); rewrite(output); main;
close(input); close(output); end.
.............. 7、有依赖的背包
program DependingPack;//有依赖的背包（简化） const
maxv=20000; maxn=3000; var
f,h:array[0..maxv]of longint; w,c,yl:array[1..maxn]of longint; n,v:longint;
procedure join(p:longint); var
j:longint; begin
for j:=v downto 0 do if j+c[p]<=v then
if h[j]+w[p]>h[j+c[p]] then h[j+c[p]]:=h[j]+w[p]; end;
procedure main; var
i,j,k,max:longint; begin
readln(n,v);
for i:=0 to v do f:=0;
for i:=1 to n do read(c,w,yl); for i:=1 to n do
if yl=0 then//以主件分组 begin
for j:=0 to v do h[j]:=0;
for j:=1 to n do if yl[j]=i then join(j);//局部01背包（构造泛化物品） for j:=v downto 0 do if j+c<=v then
h[j+c]:=h[j]+w;//加入主件 for j:=0 to c-1 do h[j]:=0; for j:=v downto 0 do for k:=v downto 0 do if j+k<=v then
if f[j]+h[k]>f[j+k] then f[j+k]:=f[j]+h[k];//DP end; max:=f[0];
for i:=1 to v do if f>max then max:=f; writeln(max); end; begin
assign(input,'Pack.in'); reset(input);
assign(output,'Pack.out'); rewrite(output); main;
close(input); close(output); end.