背包問題的三種解法代碼實(shí)現(xiàn)

1、背包問題的三種解法實(shí)驗報告實(shí)驗要求：分別用動態(tài)規(guī)劃法、回溯法、分支限界法解決0/1背包問題，了解三種算法的算法步驟并上機(jī)實(shí)現(xiàn)。實(shí)驗步驟：1 .建立一個背包問題的解法類Bag.h。bag_m為動態(tài)規(guī)劃法，bag_b為回溯法，bag_t為分支限界法。2 .建立一個排序類Sortl.h。程序的需要對背包的價值比排序。3 .由分支限界建立一個動態(tài)的最大堆及堆的各種操作和運(yùn)算類SqList.h。代碼實(shí)現(xiàn)：1 .主函數(shù)：/背包問題的解法#include <iostream>#include "Bag.h"/背包問題處理方法類using namespace std;int m

2、ain() int i,n,M; cout<<"請輸入物品個數(shù)：" cin>>n;double *m=new doublen+1;double *p=new doublen+1;cout<<"輸入每個物品的重量："for(i=1;i<=n;i+) cin>>mi;cout<<"輸入每個物品的價值："for(i=1;i<=n;i+) cin>>pi;cout<<"請輸入背包的重量："cin>>M;Bag bag

3、;/創(chuàng)建一個背包問題的解法類對象cout<<"選擇背包問題的解法，輸入 1,動態(tài)規(guī)劃法，輸入2,回溯法，輸入 3,分支限界法。"<<'n'<<"請輸入1或者2,或者輸入3:"<<""cin>>i; if(i=1) bag.bag_m(m,p,n,M); 調(diào)用動態(tài)規(guī)劃法 if(i=2) bag.bag_b(m,p,n,M); / 調(diào)用回溯法 if(i=3) bag.bag_t(m,p,n,M); /調(diào)用分支限界法 return 0;2 .排序方法類：(Filen

4、ame： Sort1.h)/合并排序類（合并排序）#include <iostream>using namespace std; struct objdouble m;double p;double v;；typedef struct obj OBJ; /定義物體的數(shù)據(jù)結(jié)構(gòu)class Sort1public:void merge_sort(OBJ a,int n) / 以物體的價值比排序 int i,s,t=1;while(t<n)s=t;t=2*s;i=0; while(i+t<n)merge(a,i,i+s-1,i+t-1,t); i=i+t;if(i+s<n

5、)merge(a,i,i+s-1,n-1,n-i);void merge(OBJ a,int p,int q,int r,int n) OBJ *bp=new OBJn;int i,j,k;i=p;j=q+1;k=0;while(i<=q&&j<=r)if(ai.v<=aj.v)bpk+=ai+;elsebpk+=aj+;if(i=q+1)for(產(chǎn)r;j+) bpk+=aj; elsefor(;i<=q;i+) bpk+=ai;k=0;for(i=p;i<=r;i+) ai=bpk+;delete bp;；3 .背包問題解法類：(Filename

6、： Bag.h)/背包問題方法類(包含三種方法)/bag_m動態(tài)規(guī)劃法/bag_b 回溯法/bag_t分支限界法#include <iostream> using namespace std;#include "Sortl.h"#include "SqList.h"class Bagpublic:/動態(tài)規(guī)劃法void bag_m(double *m,double *p,int n,int M) int i,j;int *x=new intn+1;OBJ *objs=new OBJn+1;objs0.m=0;objs0.p=0;objs0.v=

7、0;for(i=1;i<=n;i+)objsi.m=mi;objsi.p=pi;objsi.v=objsi.m/objsi.p;double *optp;optp=new double *n+1;for(i=0;i<n+1;i+)optpi=new doubleM+1; xi=0;for(i=0;i<=n;i+)optpi0=0；for(i=0;i<=M;i+)optp0i=0；for(i=1;i<=n;i+)for(j=1;j<=M；j+)if(objsi.m>j)optp皿=optpi-1j；elseoptp皿=optpi-1j；if(optpiU

8、<(optpi-1int(j-objsi.m)+objsi.P)optpiU=(optpi-1int(j-objsi.m)+objsi.p)； i=n;j=M;while(i&&j)if(optpij>optpi-1j)xi=1;j-=objsi.m;elsexi=0;i-；cout<<"輸出結(jié)果，裝入為 1 ,不裝入為0:"<<'n'for(i=1;i<=n;i+)cout<<xi<<""cout<<'n'cout<<

9、;"背包物體的總價值最大為："<<optpnM<<'n'delete x,objs;for(i=0;i<=n;i+)delete optpi;delete optp;void bag_b(double *m,double *p,int n,int M)/ 回溯法int i,j,k;int *x=new intn+1;int *y=new intn+2;double m_cur,m_est,p_cur,p_est,p_total;m_cur=0;p_cur=0;p_total=0;OBJ *objs=new OBJn+1;objs

10、0.m=0;objs0.p=0;objs0.v=0;for(i=1;i<=n;i+)objsi.m=mi;objsi.p=pi;objsi.v=objsi.m/objsi.p;yi=0;xi=0;yn+1=0;Sortl sort;sort.merge_sort(objs,n+1);/ 排序k=1;while(k>=1)p_est=p_cur;m_est=m_cur;for(i=k;i<=n;i+)m_est=m_est+objsi.m;if(m_est<M)p_est=p_est+objsi.p;elsep_est=p_est+(M-m_est+objsi.m)/ob

11、jsi.m)*objsi.p; break;if(p_est>p_total)for(i=k;i<=n;i+)if(m_cur+objsi.m<=M)m_cur+=objsi.m;p_cur+=objsi.p;yi=1;else yi=0; break;if(i>=n)if(p_cur>p_total)p_total=p_cur;k=n+1;for(j=1;j<=n；j+)xj=yj;else k=i+1;elsewhile(i>=1&&yi=0)i-；if(i<1) break;elsem_cur-=objsi.m;p_cur-

12、=objsi.p;yi=0;k=i+1;for(i=1;i<=n;i+)cout<<xi;cout<<'n'cout<<"total="<<p_total;delete x,y,objs;void bag_t(double *m,double *p,int n,int M) / 分支限界法 int i;double t;OBJ *ob=new OBJn;for(i=0;i<n;i+)obi.m=mi+1;obi.p=pi+1;obi.v=obi.m/obi.p;Sort1 sort;sort.mer

13、ge_sort(ob,n);Knapnode kna,knax,knay;/定義左節(jié)點(diǎn)和右節(jié)點(diǎn)kna.b=0;kna.k=0;kna.p=0;kna.w=0;for(i=0;i<5;i+)kna.s1i=0;for(i=kna.k,t=kna.w;i<n;i+)(if(t+obi.m<=M)(t+=obi.m;kna.b+=obi.p;else(kna.b+=(M-t)*obi.p/obi.m; break;sqlist q;SqList sq;sq.InitList_Sq(q);sq.insert(q,kna);while(q.length!=0)(kna=sq.delet

14、e_max(q);if(kna.k=5)(cout<<"the value is:"<<kna.p<<'n' for(i=0;i<5;i+)cout<<kna.s1i<<"" cout<<'n'break;knay=kna;knay.k+;knay.b=knay.p;for(i=knay.k,t=knay.w;i<n;i+)(if(t+obi.m<=M)(t+=obi.m;knay.b+=obi.p; else(knay.b+=(M-

15、t)*obi.p/obi.m; break;sq.insert(q,knay);knax=kna;if(knax.w+obknax.k.m>M)continue;knax.s1knax.k=1;knax.w+=obknax.k.m;knax.p+=obknax.k.p;knax.k+;sq.insert(q,knax);；4 .動態(tài)堆方法類(分支限界方法中用到，F(xiàn)ilename： SqList.h)/動態(tài)最大堆#include <iostream>#include "math.h"#include <iomanip> using namespa

16、ce std;#define ListInitSize 20#define ListIncrement 10const n=5;typedef structint s1n;int k;float b;float w;float p;Knapnode;typedef struct sqListKnapnode *elem;int length;int listsize;sqlist;class SqList / 動態(tài)堆類public:void InitList_Sq(sqlist &L)/n為單位元素的大小，初始化堆L.elem=(Knapnode *)malloc(ListInitSi

17、ze * sizeof(Knapnode); if(L.elem=NULL) exit(OVERFLOW);L.length=0;L.listsize=ListInitSize;void ListInsert_Sq(sqlist &L,Knapnode elem) 向堆中插入節(jié)點(diǎn)Knapnode * newbase;if(L.length>=L.listsize) newbase=(Knapnode *)realloc(L.elem,(L.listsize+ListIncrement) sizeof(Knapnode); if(newbase=NULL) exit(OVERFLO

18、W);L.elem=newbase;L.listsize+=ListIncrement;L.elem+L.length=elem;void sift_up(sqlist &L,int i) / 上移操作while(i>=2)if(L.elemi.b>L.elemi/2.b)swap(L.elemi/2,L.elemi);i/=2;else break;void sift_down(sqlist &L,int i) / 下移操作int done=0;i=2*i;while(done=0&&i<=L.length) if(i+1<=L.len

19、gth&&L.elemi+1.b>L.elemi.b) i+;if(L.elemi/2.b<L.elemi.b)swap(L.elemi/2,L.elemi);else done=1;void swap(Knapnode &a,Knapnode &b)Knapnode t;t=a;a=b;b=t;void insert(sqlist &L,Knapnode x) 插入節(jié)點(diǎn)后，并排序 ListInsert_Sq(L,x);sift_up(L,L.length);Knapnode delete_max(sqlist &L) /刪除堆中預(yù)測

20、價值的最大者 Knapnode p;p=L.elem1;swap(L.elem1,L.elemL.length);L.length-;sift_down(L,1);return p;void print(sqlist &L) / 打印堆的數(shù)據(jù)int i;for(i=1;i<=L.length;i+)cout<<L.elemi.b;；運(yùn)行方法和結(jié)果(用這三種算法分別給出實(shí)驗結(jié)果)：1.動態(tài)規(guī)劃法：粕八ZL法，麻八1,初念捌刑法,徜固0趣咆ff法._4舍2 .或著輸入3二1總集入為1,不裝入為山。元 *C： kFr otu Fi lesMlicrosoft ¥i

21、 sual StoAi o WyFroj ec t110 0 1背包物體的總價值最大為！ 15Press any key to continuemut<U前入每T物品的重重;”；For(i=1;i<=n ;i+*icin»ml;Mut<',輸入每個物品的價值="；ForCl-1：i<=n：i+)cin»pi;c口ulXU請輸入背包的重量：、 dn»M;Eq bmq"/創(chuàng)建一個背包問題的假法類 心口戊"選擇背包|可遁的解法，輸X、 cin»i;1F(1-1)t)Hg.hdg_nitm,pmn/)

22、；調(diào)用動態(tài)規(guī)劃并 iF(i=Z)b四&四_1)(%口.1/)彳“調(diào)用回溯法1FC1-3)gg_b網(wǎng)_立嘰口小,忖第用分支眼界中return 6;2.回溯法：UOULfXC" ，產(chǎn)87帽 SUULf 工4 L""1r J .euuty端人每個物品的重量：七For(i=1;i<=n;i+>dn»nl；Bute喻入每個物品的價值；七For(i=1 ;i<=r>i+> cin>>pi;sukU請輸入背包的重量；yBog gg;創(chuàng)建一個背包問題的假法類不 GOUtX<1選停音包|可莉的降擊輸入1.動i cin»i