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

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

　　 if (equal)

　　 { for (i=1;i　　 printf(“%4d”,*pt[i]);

　　 printf(“\n”);

　　 scanf(“%*c”);

　　 }

　　 for (j=VARIABLES-1;j>0;j--)

　　 if (*pt[j]>*pt[j-1]) break;

　　 if (j==0) break;

　　 for (i=VARIABLES-1;i>=j;i--)

　　 if (*pt[i]>*pt[i-1]) break;

　　 t=*pt[j-1];* pt[j-1] =* pt[i]; *pt[i]=t;

　　 for (i=VARIABLES-1;i>j;i--,j++)

　　 { t=*pt[j]; *pt[j] =* pt[i]; *pt[i]=t; }

　　 }

　　}

　　从上述问题解决的方法中，最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。

　　【问题】 背包问题

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

　　设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中，限制重量为tw。考虑一个n元组（x0，x1，…，xn-1），其中xi=0 表示第i个物品没有选取，而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n元组，就可以得到问题的解。

　　显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0～2n-1。因此，如果把0～2n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。

【算法】

　　maxv=0;

　　for (i=0;i<2n;i++)

　　{ B[0..n-1]=0;

　　 把i转化为二进制数，存储于数组B中;

　　 temp_w=0;

　　 temp_v=0;

　　 for (j=0;j　　 { if (B[j]==1)

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

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