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

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

　　# include 

　　# define MAXN 100

　　int a[MAXN];

　　void comb(int m,int k)

　　{ int i,j;

　　 for (i=m;i>=k;i--)

　　 { a[k]=i;

　　 if (k>1)

　　 comb(i-1,k-1);

　　 else

　　 { for (j=a[0];j>0;j--)

　　 printf(“%4d”,a[j]);

　　 printf(“\n”);

　　 }

　　 }

　　}

　　

　　void main()

　　{ a[0]=3;

　　 comb(5,3);

　　}

　　【问题】 背包问题

　　问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

　　设n件物品的重量分别为w0、w1、…、wn-1，物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组option[ ]，该方案的总价值存于变量maxv。当前正在考察新方案，其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品；当前方案已包含的物品的重量之和为tw；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。

　　对于第i件物品的选择考虑有两种可能：

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

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

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

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

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