朱金灿   问题描述：有不同价值、不同重量的物品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月第二次印刷）

评论