原题
题目描述 Description
背包体积为V ,给出N个物品，每个物品占用体积为Vi,价值为Wi,每个物品要么至多取1件，要么至多取mi件(mi>1) , 要么数量无限 ， 在所装物品总体积不超过V的前提下所装物品的价值的和的最大值是多少？
输入描述 Input Description
第一行两个数N,V,下面N行每行三个数Vi,Wi,Mi表示每个物品的体积，价值与数量，Mi=1表示至多取一件，Mi>1表示至多取Mi件，Mi=-1表示数量无限
输出描述 Output Description
1个数Ans表示所装物品价值的最大值
样例输入 Sample Input
2 10
3 7 2
2 4 -1
样例输出 Sample Output
22
数据范围及提示 Data Size & Hint
对于100%的数据,V <= 200000 , N <= 200
题意
题目说的很民白了。。。。
题解
这道题就是01背包，完全背包，多重背包的结合，而且数据极大。【数据大得pascal调用max函数还会TLE！！调(kan)了(le)好(ti)久(jie)才发现这个问题
倘若是01背包与完全背包的结合，这道题就挺好办的，就可以这样乱搞：
for i:=1 to n do
begin
if 01背包的情况 then for j:=m downto w[i] do f[j]:=max(f[j],f[j-w[i]]+c[i]) else
if 完全背包的情况 then for j:=w[i] to m do f[j]:=max(f[j],f[j-w[i]]+c[i]) ;
end;
可事实不是这样的，还多了一个多重背包。接下来就来说明一下怎么将多重背包转成01背包。
假定我们读入的第i个物品的数量为p[i]，重量w[i]，价值c[i]，那么p[i]个物品就可以分为数量分别为1，2，4，...，2^log2p[i]的物品，不够分直接取剩余的。
比如说，当p[i]=8，w[i]=3，c[i]=5时，可以分为如下4个物品：
1.p[1]=1; w[1]=w[i]*p[1]=3*1=3; c[1]=c[i]*p[1]=5*1=5
2.p[2]=2; w[2]=w[i]*p[2]=3*2=6; c[2]=c[i]*p[2]=5*2=10
3.p[3]=4; w[3]=w[i]*p[3]=3*4=12; c[1]=c[i]*p[3]=5*4=20
4.p[4]=1; w[4]=w[i]*p[4]=3*1=3; c[4]=c[i]*p[1]=5*1=5
这样分有什么好处呢？
如果我们不这么做，那么要将它转化为01背包就必须将p[i]分成p[i]份，每份一件物品，以满足p[i]+1种取的方法(即取0个，取1个，...，取p[i]个)，这样子的最终的效率为O(m*sigma(p[i]))【m为背包容量】，不用看，效率极低。
我们将p[i]分为log2p[i]份则恰好解决的这个问题，先看效率，缩至O(m*sigma(log2p[i]))，接着不难发现，所分成的这log2p[i]个数恰好可以拼成0..p[i]之间任意一个数，如上面p[i]=8的例子，取0件则一件不取，取1件则取p[1]或p[4]，取2件则取p[1]+p[4]或p[2]，取3件则取p[1]+p[2]或p[4]+p[2]，取4件则取p[1]+p[2]+p[4]或p[3]，取5件则取p[1]+p[3]或p[4]+p[3]，取6件，取7件，取8件我就懒得打了。。
于是将它转化为01背包后就可以套用上面的代码了。
程序：
1 var w1,w,c1,c,p1,p:array[0..10000] of int64; 2 var f:array[0..200000] of int64; 3 var top,k,n,m:int64; 4 var i,j:longint; 5 function pow(x:longint):int64;//没事敲快速幂练手感 6 begin 7 if x=0 then exit(1); 8 pow:=pow(x >> 1); 9 pow:=pow*pow; 10 if odd(x) then pow:=pow*2; 11 end; 12 begin 13 readln(n,m); 14 for i:=1 to n do readln(w[i],c[i],p[i]); 15 for i:=1 to n do 16 begin 17 if (p[i]=-1)or(p[i]=1) then//01背包或完全背包的情况 18 begin 19 inc(top);w1[top]:=w[i];c1[top]:=c[i];p1[top]:=p[i]; 20 continue; 21 end; 22 for j:=0 to trunc(ln(p[i])/ln(2))+1 do//处理多重背包的情况 23 begin 24 if p[i]=0 then break; 25 k:=pow(j); 26 if p[i]>=k then 27 begin 28 p[i]:=p[i]-k;inc(top);w1[top]:=w[i]*k;c1[top]:=c[i]*k;p1[top]:=k; 29 end else 30 if p[i]<k then//处理剩余的情况 31 begin 32 k:=p[i]; 33 inc(top);w1[top]:=w[i]*k;c1[top]:=c[i]*k;p1[top]:=k; 34 break; 35 end; 36 end; 37 end; 38 for i:=1 to top do//乱搞 39 begin 40 if p1[i]=-1 then for j:=w1[i] to m do begin if f[j]<f[j-w1[i]]+c1[i] then f[j]:=f[j-w1[i]]+c1[i]; end else 41 if p1[i]>0 then for j:=m downto w1[i] do begin if f[j]<f[j-w1[i]]+c1[i] then f[j]:=f[j-w1[i]]+c1[i]; end; 42 end; 43 writeln(f[m]); 44 end.
欢迎转载，若转载请注明出处。