背包问题:有不同价值,不同重量的物品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(); } 总结:在看参考书的例子的时候,应该多动脑筋先想一想。再进行比较,对自己有很大帮助。

|