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

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

　　 if (tw+a[i].weight<=limitW)

　　 { cop[i]=1;

　　 if (i　　 else

　　 { for (k=0;k　　 option[k]=cop[k];

　　 maxv=tv;

　　 }

　　 cop[i]=0;

　　}

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

　　 if (tv-a[i].value>maxV)

　　 if (i　　 else

　　 { for (k=0;k　　 option[k]=cop[k];

　　 maxv=tv-a[i].value;

　　 }

　　}

　　

　　void main()

　　{ int k;

　　 double w,v;

　　 printf(“输入物品种数\n”);

　　 scanf((“%d”,&n);

　　 printf(“输入各物品的重量和价值\n”);

　　 for (totv=0.0,k=0;k　　 { scanf(“%1f%1f”,&w,&v);

　　 a[k].weight=w;

　　 a[k].value=v;

　　 totV+=V;

　　 }

　　 printf(“输入限制重量\n”);

　　 scanf(“%1f”,&limitV);

　　 maxv=0.0;

　　 for (k=0;k　　 find(0,0.0,totV);

　　 for (k=0;k　　 if (option[k]) printf(“%4d”,k+1);

　　 printf(“\n总价值为%.2f\n”,maxv);

　　}

 作为对比，下面以同样的解题思想，考虑非递归的程序解。为了提高找解速度，程序不是简单地逐一生成所有候选解，而是从每个物品对候选解的影响来形成值得进一步考虑的候选解，一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况：当该物品被包含在候选解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的；反之，该物品不应该包括在当前正在形成的候选解中。同样地，仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中；反之，该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案，程序就去进一步考虑下一个物品。

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

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