贪心算法实现01背包问题_第1页
贪心算法实现01背包问题_第2页
贪心算法实现01背包问题_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、贪心算法实现01背包问题算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。具体实现过程是：首先可以设置一个备份pvu类型的数组，在不破环原数据的情况下，对此备份数组按单位重量价值从大到小的排序。依次设立两个指针i，j(其中i表示当前应该参与最佳pv值的元素指针，j表示符合约束条件的指针（单位重量价值PV最大，重量最小，不超过最大承重量约束)代码实现如下：#include using namespace std;typedef structint v;int w;float pv;pvu;void sor

2、tByPv(pvu ,int );int zeroneBags(pvu,int,int,int * );void print(pvu a,int n)for (int i=0;in;i+)coutai.w ai.v ai.pvendl;coutendl;int main()int i,maxw; int w=1,2,3,2;int v=9,10,15,6;int n=sizeof(w)/sizeof(int );const int N=n;pvu arrN;for (i=0;in;i+)arri.v=vi;arri.w=wi;arri.pv=vi*1.0/wi;int remained;cou

3、tmaxw;cout最大价值为:zeroneBags(arr,n,maxw,&remained)n还剩remained公斤空间未使用endl;return 0;void sortByPv(pvu arr ,int n) pvu t;int i,j;for (i=0;in-1;i+) for (j=0;jn-1-i;j+) if (arrj.pvarrj+1.pv) t=arrj; arrj=arrj+1; arrj+1=t; int zeroneBags(pvu arr,int n,int maxw,int *e)int i=0,j,minw,totalv=0;int avail=maxw;sortByPv(arr,n);/按最大单位重量价值PV从大到小的排序 while (avail&in)minw=i;for (j=0;jarrj.w&ji)minw=j;if (arrminw.w=avail)avail-=arrminw.w;tota

人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论