朱金灿
问题描述：有不同价值、不同重量的物品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下编译运行成功。
程序测试结果，截图如下：
参考文献：《软件设计师考试考点分析与真题详解》（张友生 周俊松 聂作明 主编 中国系统分析员顾问团 组编 飞思教育产品研发中心 监制，印次：2004年10月第二次印刷）
评论