考试网 >> IT认证 >> 水平 >> 软件指导 >> 软考常用算法设计方法(一)

发布时间：2006-06-28 04:48     点击：

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

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

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

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

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

　　 else

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

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

　　 恢复物品i不包含状态；

　　 }

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

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

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

　　 else

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

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

　　 }

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

　　物品 0 1 2 3

　　重量 5 3 2 1

　　价值 4 4 3 1

　　

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

　　

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

　　【程序】

　　# include 

　　# define N 100

　　double limitW,totV,maxV;

　　int option[N],cop[N];

　　struct { double weight;

　　 double value;

　　 }a[N];

　　int n;

　　void find(int i,double tw,double tv)

　　{ int k;

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

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

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