当前位置:   article > 正文

0/1背包问题(回溯法)_回溯法求解0-1背包问题

回溯法求解0-1背包问题

1.问题分析

        给定n种物品和一个背包容量为c的背包,物品i的重量是wi,其价值为vi,利用回溯法来实现求解如何使装入背包中的物品的总价值最大。

2.算法设计思路

(1)物品有n种,背包容量为C,用v[i]和w[i]存储第i种物品的价值和重量,用x[i]标记第i种物品是否装入背包,用bestx[i]存储第i种物品的最优装载方案;

(2)用递归函数Knapsack(i,bv,bw)来实现回溯法搜索子集树(形式参数i表示递归深度,n用来控制递归深度,形式参数bv和bw表示当前总价值和总重量,bestv表示当前最优总价值);

(3)若i>n,则算法搜索到一个叶子结点,判断当前总价值是否最优;

(4)若bv>bestv,更新当前最优总价值为当前总价值,再更新装载方案;

(5)采用for循环对物品i装与不装两种情况进行讨论(0≤j≤1):

          1)x[i]=j;

          2)若总重量不大于背包容量(即bw+x[i]*w[i]<=c),则更新当前总价值和总重量(即bw+=w[i]*x[i],bv+=v[i]*x[i]), 对物品                     i+1调用递归函数Knapsack (i+1,cp,cw) 继续进行装载;

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/795486
推荐阅读
相关标签
  

闽ICP备14008679号