數據結構-背包問題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件物品后未滿，則繼續(xù)選取第i+1件，若該件物品“太大”不能裝入，則棄之，繼續(xù)選取下一件，直至背包裝滿為止。 如果在剩余的物品中找不到合適的物品以填

2、滿背包，則說明“剛剛”裝入的物品“不合適”，應將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復，直到求得滿足條件的解，或者無解。 由于回溯求解的規(guī)則是“后進先出”，自然要用到“?！?。 進一步考慮：如果每件物品都有體積和價值，背包又有大小限制，求解背包中存放物品總價值最大的問題解-最優(yōu)解或近似最優(yōu)解。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;/*創(chuàng)建數組，儲存物品體積*/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執(zhí)行完畢"); int main() int n; seqlist *l; prin