考试网 >> IT认证 >> 等级 >> 等级动态 >> 常用算法设计方法2

发布时间：2006-07-25 12:02     点击：

（1）              考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。

（2）              考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。

    按以上思想写出递归算法如下：

try(物品i，当前选择已达到的重量和，本方案可能达到的总价值tv)

{     /*考虑物品i包含在当前方案中的可能性*/

       if(包含物品i是可以接受的)

       {     将物品i包含在当前方案中；

              if (i<n-1)

                     try(i+1,tw+物品i的重量,tv);

              else

                     /*又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/

以当前方案作为临时最佳方案保存;

                     恢复物品i不包含状态；

              }

              /*考虑物品i不包含在当前方案中的可能性*/

              if (不包含物品i仅是可男考虑的)

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。