01背包问题 第二个循环为什么是for (int v = V; v >= c[i]; --v)
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/07/15 06:05:24
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]表示的是什么?
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]表示的是什么?
![01背包问题 第二个循环为什么是for (int v = V; v >= c[i]; --v)](/uploads/image/z/3236476-4-6.jpg?t=01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98+%E7%AC%AC%E4%BA%8C%E4%B8%AA%E5%BE%AA%E7%8E%AF%E4%B8%BA%E4%BB%80%E4%B9%88%E6%98%AFfor+%28int+v+%3D+V%3B+v+%3E%3D+c%5Bi%5D%3B+--v%29)
学习精神不错
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]]
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]]