作业帮 > 综合 > 作业

01背包问题 第二个循环为什么是for (int v = V; v >= c[i]; --v)

来源：学生作业帮 编辑：拍题作业网作业帮 分类：综合作业 时间：2024/05/01 08:37:14
01背包问题 第二个循环为什么是for (int v = V; v >= c[i]; --v)
for (int v = V; v >= c[i]; --v) //c[i]可优化为bound,bound = max {V - sum c[i,...n],c[i]}
　　{
　　f[v] = (f[v] > f[v - c[i]] + w[i] f[v] :f[v - c[i]] + w[i]);
　　}
百度百科上
循环条件为什么是for (int v = V; v >= c[i]; --v)
f[v]表示的是什么?
学习精神不错
f[v]是表示包容量为v时候的价值
你的追问中有理解错误：
那么第i个物品不放的价值,肯定小于第i个物品放的价值啊?
一般理解这是正确的,但是这是一个有容量限制的问题,要是前面已经满了的话可能第i个物品再也放不进去啊,这样你的理解就错了
思路：
包的容量为v吧,第i个物品体积c[i],价值w[i],f[v]表示包容量为v时候能够装的价值
现在第i个物品还没有装：f[v]表示包中装的前i-1个物品的价值
我要装i物品的话：它占用了c[i]的容量,获得w[i]价值,那么前面的i-1个物品就只能占用v-c[i]的空间,否则现在就装不下.
这样如果装i的话,利益就是f[v-c[i]]+w[i]
所以要比较装i的价值f[v-c[i]]+w[i]和不装i的价值f[v]
你说不用比较,但你想想：v的容量装前i-1个物品的价值肯定要大于等于v-c[i]的容量装的i-1个物品吧,这样f[v-c[i]]
01背包问题 第二个循环为什么是for (int v = V; v >= c[i]; --v) V=(v'+u)/{1+[(v*u)/(c^2)] } V v？ v. -v - v - v% 算法分析与设计题目 请求解0/1/2背包问题：有1个背包、其容量为C,有n种物品（每个物品种类i都自己的重量wi和价值v 政治经济学计算,我想知道这个公式I(v+△v+m/x)=II(c+△c)里面的△v和△c是怎么来的 c=n/v中,n ,c ,v分别是什么? 个v