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

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

    问题描述：有不同价值、不同重量的物品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)

              {     temp_w=temp_w+w[j];

                     temp_v=temp_v+v[j];

              }

              if ((temp_w<=tw)&&(temp_v>maxv))

              {     maxv=temp_v;

分页:上一页  1 2 3 4 5 6 7 [8] 9 10  下一页

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

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