背包問題的貪心算法

1、貪心方法：總是對當(dāng)前的問題作最好的選擇，也就是局部尋優(yōu)。最后得到整體最優(yōu)。應(yīng)用： 1 ：該問題可以通過“局部尋優(yōu)”逐步過渡到“整體最優(yōu)”。貪心選擇性質(zhì)與“動態(tài)規(guī)劃”的主要差別。2：最優(yōu)子結(jié)構(gòu)性質(zhì)：某個問題的整體最優(yōu)解包含了“子 ”問題的最優(yōu)解。代碼如下：#include <iostream.h> struct goodinfofloat p; /物品效益float w; / 物品重量float X; /物品該放的數(shù)量 int flag; / 物品編號 ;/物品信息結(jié)構(gòu)體void Insertionsort(goodinfo goods,int n) int j,i;for(j=2;

2、j<=n;j+) goods0=goodsj;i=j-1;while (goods0.p>goodsi.p) goodsi+1=goodsi;i-;goodsi+1=goods0;/ 按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n) float cu;int i,j;for(i=1;i<=n;i+) goodsi.X=0;cu=M; /背包剩余容量 for(i=1;i<n;i+)if(goodsi.w>cu)/ 當(dāng)該物品重量大與剩余容量跳出 break;goodsi.X=1;cu=cu-goodsi.w;/

3、 確定背包新的剩余容量if(i<=n)goodsi.X=cu/goodsi.w;/ 該物品所要放的量/* 按物品編號做降序排列*/for(j=2;j<=n;j+)goods0=goodsj;i=j-1;while (goods0.flag<goodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;/cout<<" 最優(yōu)解為:"<<endl;for(i=1;i<=n;i+)cout<<" 第 "<<i<<" 件物品要放:&quo

4、t;cout<<goodsi.X<<endl;Insertionsort(goods,n);bag(goods,M,n);cout<<"press <1> to run agian"<<endl;cout<<"press <0> to exit"<<endl;cin>>j;#include<stdio.h>#include<stdlib.h>#define Max 100/* 定義棧結(jié)構(gòu)*/typedef struct li

5、st int dataMax; int top;Seqstack; /*定義一個用來存儲結(jié)果的鏈表*/typedef struct List Seqstack result; struct List * Next; Seqlist,*Pointer;void Inicial_List(Pointer p) p=(Pointer)malloc(sizeof(Seqlist);p->Next=NULL;Seqstack Push_Stack(int n,Seqstack s) s.top+;s.datas.top=n;return s;int Add_Stack(Seqstack s)Int

6、 total=0,i;if(s.top>=0) for(i=0;i<=s.top;i+)total+=s.datai;else total=0; return total;Seqstack Pop_Stack(Seqstack s)printf("%d",s.datas.top);if(s.top>=0)s.top-;return s;/*執(zhí)行回溯操作的函數(shù)*/*參數(shù)說明：n->數(shù)的總的個數(shù)，a口用來存放數(shù)的數(shù)組 水查找的總體積 */Pointer Query_Result(int n,int b,int k) int i,j;Seqstack my

7、stack;Seqlist *newnode;Pointer r,p=NULL;Inicial_List(p);r=p; for(i=0;i<n;i+) mystack.top=-1;j=i;while(j<n)if(Add_Stack(mystack)+bj<k) mystack=Push_Stack(bj,mystack);j+; else if(Add_Stack(mystack)+bj=k) mystack=Push_Stack(bj,mystack);newnode=(Pointer)malloc(sizeof(Seqlist);newnode->result

8、=mystack;newnode->Next=NULL;r->Next=newnode;r=newnode;mystack=Pop_Stack(mystack);j+;else if(Add_Stack(mystack)+bj>k)j+;return p;void Print_List(Pointer p)int i,j=0;p=p->Next;printf("welcome the outern");if(p=NULL)printf("there no resultsn");while(p!=NULL)j+;printf(&qu

9、ot;the %d result is: ",j);for(i=0;i<=p->result.top;i+) printf(" %d",p->result.datai);p=p->Next;printf("n"); printf("n");void Sort_Array(int b,int n)int i,j,temp;for(i=0;i<n;i+) for(j=0;j<n-i;j+)if(bj<bj+1) temp=bj;bj=bj+1;bj+1=temp;void main()i

10、nt i,n,k,select,aMax;Pointer head;printf("*n"); printf("1 startn2 exitn");scanf("%d",&select);while(select=1)printf("please input the total productsn");scanf("%d",&n);printf("please input the volumn of n productsn"); for(i=0;i<n;

11、i+)printf("please input the %d integers",i+1);scanf("%d",&ai);printf("n");printf("please input the volunm to putn");scanf("%d",&k);Sort_Array(a,n);head=Query_Result(n,a,k);Print_List(head);printf("*n");printf("1 startn2 exitn&q

12、uot;); scanf("%d",&select);#include<stdio.h>#include<stdlib.h>#define Max 100/* 定義棧結(jié)構(gòu)*/typedef struct list int dataMax; int top;Seqstack;/* 定義一個用來存儲結(jié)果的鏈表*/typedef struct ListSeqstack result;struct List * Next;Seqlist,*Pointer;void Inicial_List(Pointer p)p=(Pointer)malloc(si

13、zeof(Seqlist);p->Next=NULL;Seqstack Push_Stack(int n,Seqstack s) s.top+;s.datas.top=n;return s;int Add_Stack(Seqstack s) int total=0,i;if(s.top>=0)for(i=0;i<=s.top;i+) total+=s.datai; elsetotal=0;return total;Seqstack Pop_Stack(Seqstack s)printf("%d",s.datas.top);if(s.top>=0)s.

14、top-; return s;/*執(zhí)行回溯操彳的函數(shù) */*參數(shù)說明：n->數(shù)的總的個數(shù)，a口用來存放數(shù)的數(shù)組，k查找的總體積*/ Pointer Query_Result(int n,int b,int k)int i,j;Seqstack mystack;Seqlist *newnode;Pointer r,p=NULL;Inicial_List(p);r=p;for(i=0;i<n;i+)mystack.top=-1;j=i;while(j<n)if(Add_Stack(mystack)+bj<k)mystack=Push_Stack(bj,mystack);j+

15、;else if(Add_Stack(mystack)+bj=k)mystack=Push_Stack(bj,mystack);newnode=(Pointer)malloc(sizeof(Seqlist);newnode->result=mystack;newnode->Next=NULL;r->Next=newnode;r=newnode;mystack=Pop_Stack(mystack);j+;else if(Add_Stack(mystack)+bj>k)j+;return p;void Print_List(Pointer p)int i,j=0;p=p-&

16、gt;Next;printf("welcome the outern");if(p=NULL)printf("there no resultsn");while(p!=NULL)j+;printf("the %d result is: ",j); for(i=0;i<=p->result.top;i+) printf(" %d",p->result.datai);p=p->Next;printf("n");printf("n");void Sort_A

17、rray(int b,int n)int i,j,temp;for(i=0;i<n;i+) for(j=0;j<n-i;j+)if(bj<bj+1)temp=bj;bj=bj+1;bj+1=temp;void main()int i,n,k,select,aMax; Pointer head;printf("*n");printf("1 startn2 exitn"); scanf("%d",&select); while(select=1)printf("please input the total productsn");scanf("%d",&n);printf("please input the volumn of n productsn");for(i=0;i<n;i+) printf("please input the %d integers",i+1);scanf(&q