3269 混合背包
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题解
查看运行结果
题目描述 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
题目很简单，但是数据很恐怖，第一次打妥妥的全tle，01背包和完全背包可以按照老方法写，多重背包用了一点点小优化（我也搞不太明白，但是背下来就好）。
24到39行
是最重要最有价值的部分！！！
program mys;
var i,j,k,m,n,kk:longint;
v,w,t:array[0..500]of longint;
f:array[0..500000]of int64;
begin
readln(n,m);
for i:=1 to n do
begin
readln(v[i],w[i],t[i]);
if t[i]=1 then
begin
for j:=m downto v[i] do
if f[j-v[i]]+w[i]>f[j] then
f[j]:=f[j-v[i]]+w[i];
end;
if t[i]=-1 then
begin
for j:=v[i] to m do
if f[j-v[i]]+w[i]>f[j] then
f[j]:=f[j-v[i]]+w[i];
end;
if t[i]>1 then //最重要的部分！！！
begin
kk:=1;
while kk<=t[i] do
begin
for j:=m downto kk*v[i] do
if f[j-kk*v[i]]+kk*w[i]>f[j] then
f[j]:=f[j-kk*v[i]]+kk*w[i];
t[i]:=t[i]-kk;
kk:=kk*2;
end;
if t[i]>0 then
for j:=m downto t[i]*v[i] do
if f[j-t[i]*v[i]]+t[i]*w[i]>f[j] then
f[j]:=f[j-t[i]*v[i]]+t[i]*w[i];
end;
end;
writeln(f[m]);
end.