背包问题另解

背包问题：有不同价值，不同重量的物品n件，求这 件物品中选取一部分，

是选中物品的总重量不超过指定的限制重量，但选取的物品总价值要最大。

解题思想：利用递归求出所选取的物品的所有可能，将满足限制重量条件的进行复值，

Value始终存放最大的物品总价值，Weight是满足条件的物品的总重量，以下

是我自己写的一段代码，与《系统设计师》教程中的思路是不一样的，代码

经过编译的，而且运行结果正确：

#include<stdio.h>

#include<stdlib.h>

#define MAX 100

struct Bag

{ int weight;

int value;

}Bag[MAX];

int a[MAX];

int Value=0;

int Weight;

int comb(int m,int k)

{int i,j;

int wei,val;

for(i=m;i>=k;i--)

{ a[k]=i;

if(k>1)

comb(i-1,k-1);

else

{ wei=0; //预值0

val=0;

for(j=a[0];j>0;j--) //每一种组合求它们的重量和价值

{ wei=wei+Bag[a[j]].weight;

val=val+Bag[a[j]].value;

}

if(wei<=Weight&&val>Value) //判断是否满足条件进行附值

Value=val;

}

}

return Value;

}

void main()

{ int num,subnum;

int l,

clrscr();

printf("\nenter the number of total Bag:"); //输入背包的总个数

scanf("%d",&num);

printf("\nenter %d number Bag'weight and Bag'value(sample *,* )\n",num); //输入背包的重量和价值

for(l=1;l<=num;l++)

scanf("%d,%d",&Bag[l].weight,&Bag[l].value);

printf("\nenter the subnumber of the Bag:"); //输入要求背包的个数

scanf("%d",&subnum);

printf("\nenter the Weight for %d Bag:",subnum); //输入满足条件的重量

scanf("%d",&Weight);

a[0]=subnum;

printf("\nthe max value is:%d",comb(num,subnum));

getch();

}

总结：在看参考书的例子的时候，应该多动脑筋先想一想。再进行比较，对自己有很大帮助。