已阅读5页,还剩5页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。应用: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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年书店行业社交分享报告
- 2026年区块链技术在金融行业的应用与挑战分析
- 2026年旅游行业后疫情时代恢复策略报告
- 2026年养老产业市场潜力报告:华东、华南、华北、西南市场分析
- 2026年环保产业报告及绿色发展理念
- 2026年食品工业中农残兽残处理技术研究报告
- 2026年房地产产业链国产化与市场前景报告
- 2026年物流行业预算管理创新报告
- 2026年虚拟数字人在博物馆展览中的应用报告
- 患者心理康复课件
- 煤矿测量新手培训课件
- 义工考核管理制度
- 言语治疗共鸣障碍课件
- 福建莆田市拔尖人才选拔考试六年级试卷及答案
- 电力行业技术服务合同
- JGJ52-2006 普通混凝土用砂、石质量及检验方法标准
- 四川省民族地区旅游产业发展综合规划
- 主题班会调整心态缓解压力省公开课一等奖全国示范课微课金奖课件
- 病毒基因组课件
- 中裕能源项目短视频运营方案
- 三年级英语课标解读课件
评论
0/150
提交评论