背包问题的贪心算法.doc

贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。代码如下：#include struct goodinfofloat p;/物品效益float w;/物品重量float X;/物品该放的数量int flag;/物品编号;/物品信息结构体void Insertionsort(goodinfo goods,int n)int j,i;for(j=2;jgoodsi.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;icu)/当该物品重量大与剩余容量跳出break;goodsi.X=1;cu=cu-goodsi.w;/确定背包新的剩余容量if(i=n)goodsi.X=cu/goodsi.w;/该物品所要放的量/*按物品编号做降序排列*/for(j=2;j=n;j+)goods0=goodsj; i=j-1;while (goods0.flaggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;/cout最优解为:endl;for(i=1;i=n;i+)cout第i件物品要放:;coutgoodsi.Xendl;void main()cout|-运用贪心法解背包问题-|endl;cout|-power by zhanjiantao(028054115)-|endl;cout|-|endl;int j;int n;float M;goodinfo *goods;/定义一个指针while(j)coutn;goods=new struct goodinfo n+1;/coutM;coutendl;int i;for(i=1;i=n;i+)goodsi.flag=i;cout请输入第igoodsi.w;cout请输入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比coutendl;Insertionsort(goods,n);bag(goods,M,n);coutpress to run agianendl;coutpress to exitj;#include#include#define Max 100/*定义栈结构*/typedef struct listint dataMax;int top;Seqstack; /*定义一个用来存储结果的链表*/typedef struct ListSeqstack 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 total=0,i; if(s.top=0) for(i=0;i=0)s.top-;return s;/*执行回溯操作的函数*/*参数说明：n-数的总的个数，a用来存放数的数组,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;in;i+)mystack.top=-1; j=i;while(jn) if(Add_Stack(mystack)+bjresult=mystack;newnode-Next=NULL;r-Next=newnode;r=newnode;mystack=Pop_Stack(mystack);j+; else if(Add_Stack(mystack)+bjk) 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(the %d result is: ,j);for(i=0;iresult.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;in;i+)for(j=0;jn-i;j+) if(bjbj+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;in;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);scanf(%d,&select); #include#include#define Max 100/*定义栈结构*/typedef struct listint dataMax;int top;Seqstack; /*定义一个用来存储结果的链表*/typedef struct ListSeqstack 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 total=0,i; if(s.top=0) for(i=0;i=0)s.top-;return s;/*执行回溯操作的函数*/*参数说明：n-数的总的个数，a用来存放数的数组,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;in;i+)mystack.top=-1; j=i;while(jn) if(Add_Stack(mystack)+bjresult=mystack;newnode-Next=NULL;r-Next=newnode;r=newnode;mystack=Pop_Stack(mystack);j+; else if(Add_Stack(mystack)+bjk) 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(the %d result is: ,j);for(i=0;iresult.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;in;i+)for(j=0;jn-i;j+) if(bjbj+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;in;i+)printf(please inpu