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

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

                     if (i<n-1)

                            try(i+1,tw,tv-物品i的价值)；

                     else

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

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

       }

       为了理解上述算法，特举以下实例。设有4件物品，它们的重量和价值见表：

物品0123

重量5321

价值4431

 

    并设限制重量为7。则按以上算法，下图表示找解过程。由图知，一旦找到一个解，算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找，而是立即终止该分支，并去考察下一个分支。

Try(0,0,12)

Try(1,5,12)

Try(1,0,8)

Try(2,5,8)

Try(3,7,8)

Try(2,3,8)

Try(3,5,8)

不能得到更好的解

不能得到更好的解

超重

不能得到更好的解

得到解：(1,0,1,0)

maxv=7

得到解：(0,1,1,1)

maxv=8

不能得到更好的解

超重

按上述算法编写函数和程序如下：

【程序】

# include <stdio.h>

# define   N     100

double     limitW,totV,maxV;

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

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