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

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

#include

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

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

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

{

int i;

for(i=0;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: ");

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

printf("please input tw:");

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

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

for(i=0;i

{

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

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

}

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

for(i=0;i

{

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

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

}

maxv = 0;

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

for (i=0;i

{

for (j=0;j

{

b[j] = 0;

}

conversion(i,b);

temp_v = 0;

temp_w = 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))

{

for (j=0;j

{

temp[j] = 0;

}

maxv = temp_v;

for (j=0;j

{

temp[j] = b[j];

}

}

}

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

printf("the selection is: ");

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

for (j=0;j

{

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

}

}

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

程序测试结果，截图如下：