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

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

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

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

       maxv=0.0;

       for (k=0;k<n;k++)  cop[k]=0;

       find(0,0.0,totV);

       for (k=0;k<n;k++)

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

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

}

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

【程序】

# include <stdio.h>

# define   N     100

double     limitW;

int    cop[N];

struct      ele   {     double     weight;

                            double     value;

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

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