最佳装载背包问题--贪心算法.doc_第1页
最佳装载背包问题--贪心算法.doc_第2页
最佳装载背包问题--贪心算法.doc_第3页
全文预览已结束

下载本文档

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

文档简介

贪心法求解 最佳装载 背包问题描述：对于容量为c的背包进行装载，从n个物品中选择装入背包的物品，每个物品i的重量和价值分别为wi和pi。在背包中物品的总重量不超过背包容量的前提下，求装入物品价值最高的装载法。输入：5 20/物品的数量和背包的容量6 3/第一个物品的重量和价值2 5/3 810 67 4输出：01110.714286算法如下：#include #include struct goodinfo/物品结构体 float p;/价值 float w;/重量 float x;/数量 int flag;/标志变量;void Insertionsort(struct goodinfo goods,int n)/将物品根据价值排序 int i,j; for(j=2;jgoodsi.p)/找到位置后退出 goodsi+1=goodsi;/错位 i-; goodsi+1=goods0;/找到位置后将比较的对象覆盖 void bag(struct 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; printf(最优解为：n); for(i=1;i=n;i+) printf(第%d件物品要放：%fn,i,goodsi.x); int main() int j=1,n,i; float M; while(j) system(cls); printf(输入物品的总数：); scanf(%d,&n); struct goodinfo goodsn+1;/动态定义结构体数组的大小 printf(背包最大容量：); scanf(%f,&M); for(i=1;i=n;i+) goodsi.flag=i; printf(weight input:); scanf(%f,&goodsi.w); printf(price input:); scanf(%f,&goodsi.p); goodsi.p/=goodsi.w; Insertionsort(goods,n); bag(goods,M,n); printf(press
人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

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

最新文档

评论

0/150

提交评论