主题：求各位大牛教教我这个背包
wangminrui0804
[专家分：30] 发布于 2010-11-07 17:51:00
有n件物品（编号依次为1~n）和m只相同的背包，每件物品的重量分别为w[i]，每只最大背包承重为t。把尽可能多的物品放进背包里。
要求是：
1. 一件物品不能拆开放在两个或更多的背包里；
2. 物品必须编号顺序放进背包里，也就是说如果把第i件物品放进某个背包后，就不能再把编号小于i的物品放进任何背包。
输入文件
第一行，三个整数:n,t,m
第二行，n个整数，按编号给出每件物品的重量w[i]
输出文件
一个整数，表示最多可以装进m只背包里的物品数量。
样例输入：
4 5 2
4 3 4 2
样例输出：
3
回复列表 （共4个回复）
沙发
Tennokare [专家分：80] 发布于 2011-02-22 00:10:00
已有稿,明天贴. 幸亏这个不是noip背包问题..
板凳
Tennokare [专家分：80] 发布于 2011-02-22 18:37:00
审错题了.其实是..变异版.
直接在网上搜到答案贴了..
改进的状态表示描述为：
g[i,j]=(a, b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i件武器中选取j件所需的最少背包为：a个背包另加b容量。
状态转移方程为：
g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}
其中(a, b)+long[i]=(a’, b’)的计算方法为：
当b+long[i] ≤t时： a’=a; b’=b+long[i];
当b+long[i] ＞t时： a’=a+1; b’=long[i];
规划的边界条件：
当0≤i≤n时，g[i,0]=(0,0)
题目所求的最大值是：answer=max{k| g[n, k]≤(m-1,t)}
可用f[i,j]=a,g[i,j]=b来做
详见：动态规划算法的优化技巧---2001毛子青论文
3 楼
Tennokare [专家分：80] 发布于 2011-02-22 19:05:00
var n,m,i,j,n2,vv,ww,p,tt:longint;
w,v,t:array[1..1000] of longint;
// t:jian shu
f:array[0..100000] of longint;
begin
readln(n,m); n2:=0;
for i:=1 to n do
begin
read(ww,vv,tt); p:=1;
while tt>=p do
begin
inc(n2); w[n2]:=p*ww; v[n2]:=p*vv;
tt:=tt-p;
p:=p shl 1;
end;
if tt<>0 then
begin
inc(n2); w[n2]:=tt*ww; v[n2]:=tt*vv;
end;
end;
n:=n2;
for i:=0 to m do f[i]:=0;
for i:=1 to n do
for j:=m downto w[i] do
if f[j]<f[j-w[i]]+v[i] then
f[j]:=f[j-w[i]]+v[i];
writeln(f[m]);
end.
直接贴上.
4 楼
Tennokare [专家分：80] 发布于 2011-03-04 23:18:00
卖广告的么?楼上.
我来回复
您所在位置：