数据结构-背包问题4页

1、背包问题的求解1.问题描述 假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+wm=T，要求找出所有满足上述条件的解。 例如：当T=10，各件物品的体积1,8,4,3,5,2时，可找到下列4组解： (1,4,3,2) (1,4,5) (8,2) (3,5,2)。2.实现提示 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后，顺序选取物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。 如果在剩余的物品中找不到合适的物品以填

2、满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”，自然要用到“栈”。 进一步考虑：如果每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值最大的问题解-最优解或近似最优解。3 题目源代码#define maxsize 1024#define null 0#include"stdio.h"#include"conio.h"#include"stdio.h"typedef struct int la

3、st; int datamaxsize;seqlist; /定义顺序表结构体typedef struct int top; int sum; int datamaxsize;seqstack; /定义栈结构体seqstack *init_seqstack() seqstack *s; s=new seqstack; if(!s) printf("空间不足"); return null; else s->top=-1; s->sum=0; return s; /栈初试化int empty_seqstack(seqstack *s) if (s->top=-1

4、) return 1; else return 0; /判断空栈int push_seqstack(seqlist *l,int i,seqstack *s) /入栈 if(s->top=maxsize-1) return 0; else s->top+; s->datas->top=i; /顺序表中第i 个元素，i 入栈 s->sum=s->sum+l->datai; /栈中sum加和！ return 1; int pop_seqstack(seqlist *l,seqstack *s,int *x) /出栈 if(empty_seqstack(s)

5、 return 0; else *x=s->datas->top; s->sum=s->sum-l->datas->datas->top; s->top-; return 1; seqlist *init_seqlist() seqlist *l; int x=1; l=new seqlist; l->last=0; printf("-n请依次输入个物品的大小，输入0结束。n-n"); scanf("%d",&x); while(x!=0) l->datal->last=x; l-

6、>last+; scanf("%d",&x); return l;/*创建数组，储存物品体积*/void knapsk(int n,seqlist *l) seqstack *s; int flag=1; int i=0; int t; s=init_seqstack(); /初始化栈命名为S while(flag!=0) while(i<=l->last) push_seqstack(l,i,s); if(s->sum=n) printf("-n可行的解是:"); for(t=0;t<=s->top;t+) printf("%d ",l->datas->datat); printf("n"); pop_seqstack(l,s,&i); i+; else if(s->sum>n) pop_seqstack(l,s,&i); i+; else i+; while(i=l->last+1) flag=pop_seqstack(l,s,&i);i+;if(flag=0)printf("-n执行完毕"); int main() int n; seqlist *l; prin