动态规划,0-1背包问题
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/05/14 14:14:15
动态规划,0-1背包问题
在背包问题九讲中p01 01背包中有这样一段话:
一个常数优化
前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进.由于只需要最后f[v]的值,倒推前一个物品,其实只要知道f[v-w[n]]即可.以此类推,对以第j个背包,其实只需要知道到f[v-sum{w[j..n]}]即可,即代码中的 for i=1..N for v=V..0 可以改成 for i=1..n bound=max{V-sum{w[i..n]},c[i]} for v=V..bound 这对于V比较大时是有用的.
for i=1..n bound=max{V-sum{w[i..n]},c[i]} for v=V..bound 这个循环到底是怎么回事?请大牛们帮我讲解一下.
不要发代码啊.只要讲解一下就行.我不理解这个循环的运行.
在背包问题九讲中p01 01背包中有这样一段话:
一个常数优化
前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进.由于只需要最后f[v]的值,倒推前一个物品,其实只要知道f[v-w[n]]即可.以此类推,对以第j个背包,其实只需要知道到f[v-sum{w[j..n]}]即可,即代码中的 for i=1..N for v=V..0 可以改成 for i=1..n bound=max{V-sum{w[i..n]},c[i]} for v=V..bound 这对于V比较大时是有用的.
for i=1..n bound=max{V-sum{w[i..n]},c[i]} for v=V..bound 这个循环到底是怎么回事?请大牛们帮我讲解一下.
不要发代码啊.只要讲解一下就行.我不理解这个循环的运行.
相当于一个滚动数组的处理
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]);
}
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]);
}
动态规划的0-1背包问题,请高手解释下代码
求动态规划0/1背包问题的经典习题及测试数据
0-1背包问题的多种解法代码(动态规划、贪心法、回溯法、分支限界法)
分别用贪心算法和动态规算法求解0/1背包问题的最优解和最大收益
背包问题的算法登上算法、递归算法、贪婪算法、动态规划算法利用matlab编程实现我把我仅有的分都给了
用动态规划,分治法,回溯发,分枝限界法解下列0-1背包为题例题:n=3,w=[100,14,10],p=[20,18,1
0-1背包问题的测试数据
动态规划算法
pascal 0/1背包和完全背包的差别?
Lingo求解0-1规划的问题
lingo求0-1规划问题
0-1规划用lingo编程问题