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

分享到

【作者】闫建红
【刊名】电脑开发与应用
【作者单位】太原师范学院
【年份】2005
【卷号】第18卷
【期号】第8期
【页码】63
【ISSN】1003-5850
【关键词】背包问题算法研究计算机定义物品价值
【摘要】 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.采用递归...
【文献类型】期刊