对背包问题的计算机算法研究

<正>1问题定义背包问题定义:设有不同价值不同重量的物品n件。求从这n件物品中选取部分的方案,使得重量之和不超过指定的限制,但是价值之和最大。上述问题的形式化描述如下:极大化∑PiXi约束条件∑WiXi≤M其中Xi=0或1,Pi≥0,Wi>0,1≤j≤n背包问题是已经证明了的NP完全问题,这意味着我们有可能在多项式时间内求得其最优解。回溯法是解决NP完全问题的常用方法之一。2问题解法2.1算法思想设number件物品的重量放在数组a[i].weight,物品的价值放在数组a[i].value.采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于option[i],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[i]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值设为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv时,该方案不会再被考察。这同时保证函数后找到的方案一定比前面的方案更好。