time 
设为首页】【收藏本站
当前位置: 主页 > 程序设计 > C\C++\VC > C语言 > 使用穷举法解决0—1背包问题

使用穷举法解决0—1背包问题

时间:2009-09-20 23:31 点击:591次 字体:[ ]




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

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

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

    下面是我据此思路编的一个小程序。

 #include <stdio.h>

#include <math.h>

 

#define MAX 100                      // 限定最多物品数

/*将n化为二进制形式,结果存放到数组b中*/

void conversion(int n,int b[MAX])

{

 int i;

for(i=0;i<MAX;i++)

{

b[i] = n%2;

n = n/2;

if(n==0)break;

}

 

}

 

void main()

{

int i,j,n,b[MAX],temp[MAX];

float tw,maxv,w[MAX],v[MAX],temp_w,temp_v;

printf("please input n:\n");

scanf("%d",&n);   // 输入物品个数

printf("please input tw:");

scanf("%f",&tw);    // 输入背包的限制重量

/*输入各个物品的重量*/

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

{

  printf("please input the weight of w[%d]:\n",i);

  scanf("%f",&w[i]);

}

/*输入各个物品的价值*/

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

{

printf("please input the value of v[%d]:\n",i);

scanf("%f",&v[i]);

}

maxv = 0;

/*穷举2n个可能的选择,找出物品的最佳选择*/

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

{

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

       {

              b[j] = 0;

       }

       conversion(i,b);

       temp_v = 0;

       temp_w = 0;

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

       {

       if (b[j]==1)

       {

                 temp_w = temp_w+w[j];

                 temp_v = temp_v + v[j];

       }

       }

/*试探当前选择是否是最优选择,如果是就保存下来*/

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

       {

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

       {

              temp[j] = 0;

       }

              maxv = temp_v;

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

{

   temp[j] = b[j];

}

       }

}

printf("the max values is %f:\n",maxv); // 输出放入背包的物品的最大价值

printf("the selection is:\n");

/*输出物品的选择方式*/

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

{

 

       printf("%d   ",temp[j]);

}

}

 

    程序在VC6.0,win xp下编译运行成功。

    程序测试结果,截图如下:


使用穷举法解决0—1背包问题_www.fengfly.com



 



本文地址 : http://www.fengfly.com/plus/view-77281-1.html
标签: 穷举法
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:
本栏分类