回溯法求解01背包问题《小过》之《同人》问行人

来源：蜘蛛抓取(WebSpider) 时间：2016-04-06 10:40 标签： 蚁群算法求解tsp问题

本程序是用Java开发的使用回溯法解决01背包问题。程序比较易懂输入分三行，第一行是物品数量N和背包容量C第二行是物品重量数组，第三行是价值重量数组然后输出朂优解。

回溯法解决01背包问题（加剪枝condition函數） 评分:

该程序用C++实现是对简单的回溯法解决01背包问题的改进，通过加一个剪枝函数condition 可大大减少递归的次数达到较大程度提高效率的目的。

         给定n种物品（每种物品仅有一件）和一个背包物品i的重量是wi ，其价值为pi 背包的容量为w。问应如何选择物品装入背包使得装入背包中的物品的总价值最大？

        要想得到朂优解就要在效益增长和背包容量消耗两者之间寻找平衡。也就是说总应该把那些单位效益最高的物体先放入背包。

背包问题可看做昰一种回溯：


因此可用回溯方法解决。

回溯方法解决背包问题：

//与之前的物品相比 有无冲突 //无冲突添加至解路径 // 如果是最后一行 成功找到一个解 //如果不是最后一行 则判断i+1行 //第i+1行存在合适位置

或 不更新与还原相关变量， 而是根据已知信息推导相关变量值

//根据已知 推倒相关參数值 //与之前的物品相比 有无冲突 //无冲突添加至解路径 // 如果是最后一行 成功找到一个解 //如果不是最后一行 则判断i+1行 //第i+1行存在合适位置

// 判斷节点（I,j）是否为解路径上的节点,其中：

//   i表示解路径上的第i个测试节点、j表示该节点的某个候选值

   更新相关参数值（假定选择了此候选值j，因此更新受影响的参数值）；

   与0—(i-1) 层进行判断看是否与以遍历的节点有冲突

  若是最后一层，则成功找到一条解路径返回TRUE；

  若不是最後一层，则判断第i+1层是否有正确的节点

我要回帖

更多关于 蚁群算法求解tsp问题 的文章

 

随机推荐