C语言：背包问题(数据结构)

C语言：背包问题(数据结构)

详细程序代码如下:用VC6.0编译.保存代码时,以.C为后缀名下面是一组测试数据:请输入背包能容纳的最大重量：20请输入物品个数：10请输入每一个物品的重量和价值：1,11,2,22, 3,33.....10,100结果是正确的.#include#include#include#define NUMBER 20/*最大物品数量*/#define TRUE 1#define FALSE 0struct Record/*本结构体用于保存每一次结果*/{ int totalWeight;/*本次结果的总价值*/ int goods[NUMBER];/*本次结果对应的下标*/ struct Record *next;};struct Record *headLink;struct Record result;int stack[NUMBER];int top;int weight[NUMBER];/*保存物品重量的数组*/int value[NUMBER];/*保存对应（下标相同）物品的价值*/int knapproblen(int n,int maxweight,int weight[]);void CreateHeadLink(void);struct Record *MallocNode(void);void InsertOneNode(struct Record *t);void GetResult(void);void ShowResult(void);void main(){ int n,i; int maxWeight;/*背包能容纳的最大重量*/ printf("请输入背包能容纳的最大重量：\n"); scanf("%d",&maxWeight); printf("请输入物品个数：\n"); scanf("%d",&n); printf("请输入每一个物品的重量和价值：\n"); for(i=0;i0)&&(i<=n))/*当还可以装下物品，且物品没有用完时*/ { if((maxweight-weight[i]==0)||(maxweight-weight[i]>0)&&(i0;tempTop--,j++) { p->totalWeight+=value[stack[tempTop]];/*得到本次结果的总价值*/ p->goods[j]=stack[tempTop];/*得到本次结果对应的物品下标*/ } InsertOneNode(p);/*加到链表中*/ maxweight=maxweight-weight[i]; } if(maxweight==0)/*能装入包中*/ { return TRUE; } else if((i==n)&&(top>0))/*继续测试*/ { i=stack[top]; top=top-1; maxweight=maxweight+weight[i]; } i++; } return FALSE;}/************************************函数功能：建立链表表头************************************/void CreateHeadLink(void){ struct Record *p; p=(struct Record*)malloc(sizeof(struct Record)); headLink=p; p->next=NULL;}/************************************函数功能：申请一个新结点，并将其初始化************************************/struct Record *MallocNode(void){ struct Record *p; int i; p=(struct Record*)malloc(sizeof(struct Record)); if(p==NULL) return NULL; p->totalWeight=0;/*初始化总价值为0*/ for(i=0;igoods[i]=-1;/*初始化下标为-1，即无效*/ p->next=NULL; return p;}/************************************函数功能：在链表的结尾处增加一个结点************************************/void InsertOneNode(struct Record *t){ struct Record *p; p=headLink; while(p->next) { p=p->next; } p->next=t;}/************************************函数功能：遍历链表，找总价值最大的结点保存到result中************************************/void GetResult(void){ struct Record *p; int i; result.totalWeight=headLink->next->totalWeight;/*先将第一个结点当作"最佳"结果*/ for(i=0;inext->goods[i]==-1) break; result.goods[i]=headLink->next->goods[i]; } p=headLink->next->next; while(p)/*查找最佳结果*/ { if(p->totalWeight>result.totalWeight)/*如果发现p点价值比当前结果还大，则将p又作为最佳结果*/ { result.totalWeight=p->totalWeight; for(i=0;igoods[i]==-1) break; result.goods[i]=p->goods[i]; } } p=p->next; }}/***************************显示最佳结果*******************************/void ShowResult(void){ int i; printf("最佳装载如下：\n"); for(i=0;i