经典的0-1背包用动态规划解，加上什么条件之后，会变
编辑： admin 2017-27-02
-
4
把物品平均分到n个包裹中能否实现,参照vijos上的“双塔问题”
类似问题
类似问题1：求动态规划0/1背包问题的经典习题及测试数据
这是NOIP2005普及组第三题
描述 Description
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师.为此,他想拜附近最有威望的医师为师.医师为了判断他的资质,给他出了一个难题.医师把他带到一个到处都是草药的山洞里对他说：“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值.我会给你一段时间,在这段时间里,你可以采到一些草药.如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大.”
如果你是辰辰,你能完成这个任务吗?
输入格式 Input Format
输入的第一行有两个整数T（1
类似问题2：动态规划,0-1背包问题在背包问题九讲中p01 01背包中有这样一段话：一个常数优化前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进.由于只需要最后f[v]的值,倒推前一个物品,其实只
相当于一个滚动数组的处理
for i=1..n bound=max{V-sum{w[i..n]},c[i]} for v=V..bound
f[i][j]=max{f[i-1][j-w[i]]+c[i],f[i-1][j]}
现在我们处理好了
f[i][0...V]
现在处理f[i+1][0...V]时...
我们发现f[i-1][0...V]已经没用了
可是还站着内存..所以只需要一维..在状态转移时滚动就行了
而f[i][j]只与f[i-1][j]和f[i-1][j-w[i]]有关
滚动就像
f[j]只与f[j]和f[j-w[i]]有关
而如果bound...V去循环
会提早改了某个j-w[i]
所以要V...bound去循环
sum[N]=c[N];
for(int i=N-1;i>=1;i--)
sum[i]=sum[i+1]+c[i];//预处理得到sum数组
for(int i=1;ic[i])?(V-sum[i]):c[i];
for(int j=V;j>=low;j--)
f[j]=(f[j]>f[j-c[i]])?(f[j]):(f[j-c[i]]+w[i]);
}
类似问题3：详细解析动态规划与0-1背包问题,怎么理解,要易懂的,我将感激不尽!
01背包 2个状态
一个背包只有取或不取
前I个背包去装J的空间
考虑2种情况 F[I,J]:=MAX ( F[I-1,J],F[I-1,J-V[I]]+W[I])
F[I-1,J]表示第I个不取 则F[I,J]与用前I-1个装J相同
F[I-1,J-V[I]]+W[I]表示第I个取 即用前I-1个装J-V[I] （表示前I-1 装J-V[I])
然后再加上第I个的价值
这两个取最大的
fillchar(a,sizeof(a),0);
FOR I:=1 TO N DO
FOR J：=1 to m do
if (j-v[i]>=0)and( [I-1,J-V[I]]+W[I]> F[I-1,J]) then f[i,j]:=[I-1,J-V[I]]+W[I]
else f[i,j]:=f[i-1,j];
writeln(f[n,m]);
初始化全赋值为0 数组从0开始
你可以去看看背包9讲 百度文库有
去RQ 或TYVJ 做些题就行了 必须做题
类似问题4：动态规划的0-1背包问题,请高手解释下代码算法如下：void Knapsack(Type v,int w,int c,int n,Type * * m){int jMax=min(w[n]-1,c);for(int j=0;j
这是清华算法设计C++描述上的代码吧?我正巧读过.
简单解释一下吧 在解释之前你要知道动态规划是一个自底向上的过程
这个算法用到了一个二维数组m[][] 来存储各个坐标的价值信息 所以横坐标表示背包号码 纵坐标表示背包容量从1到c
注意该算法只能限制c是整数且每个背包的重量也是整数.
然后int jMax=min(w[n]-1,c);找出w[n]-1和 c之间的小者.
for(int j=0;j
类似问题5：动态规划的01背包问题,来自背包九讲上的一段：-------------------------------------------------------------------------------------------------------有N件物品和一个容量为V的背包.第i件物品的费用是c[i],价值是w[i[数学科目]
注意到原来每次f[i][v]只用了一次,所以现在f[v]相当于原来的f[v],
上次循环保存的f[v]相当于原来的f[i-1][v]
如果从0做到V的话,没有重复限制,会从v->v+c[i]->v+2*c[i]加上去,本次循环的c[i]也会加上