算法设计背包问题_第1页
算法设计背包问题_第2页
算法设计背包问题_第3页
全文预览已结束

下载本文档

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

文档简介

算法实验报告 -背包问题实验目的1掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。2熟练掌握分阶段的和递推的最优子结构分析方法。3学会利用动态规划算法解决实际问题。问题描述：给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，背包的容积d，物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出为最大的总价值。问题分析:标准0-1背包问题，MaxV表示前i个物品装入容量为j的背包中时所能产生的最大价值，结构体objec表示每一个可装入物品，其中w表示物品的重量，v表示物品的价值。如果某物品超过了背包的容量，则该物品一定不能放入背包，问题就变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值；如果该物品能装入背包，问题就变成i-1个物品装入容量为j-objeci.w的背包所能产生的最大价值加上物品i的价值objeci.v.复杂性分析时间复杂度，最好情况下为0，最坏情况下为：（abc）源程序#include #include #include#include #includeint V 200200200;int max(int a,int b) if(a=b) return a; else return b; int KnapSack(int n,int w,int z,int v,int x,int c,int b) int i,p,q;for(i=0;i=n;i+)Vi00=0; for(p=0;p=c;p+)for (q=0;q=b;q+)V0pq=0; for(i=0;i=n-1;i+)for(p=0;p=c;p+)for(q=0;q=b;q+)if(pwi&q=0;i-)if(VipqVi-1pq)xi=1; p=p-wi; q=q-zi;elsexi=0; cout选中的物品是:;for(i=0;in;i+)cout xi;coutendl;int r=0;for(i=0;in;i+)if(xi=1) r+=vi;else r+=0;return r;void main()int mv; int w150; int z150; int v150; int x150;int n,i;int c;int b;/背包最大容量和容积cout请输入背包的最大容量:c;cout请输入背包的最大容积:b;cout输入物品数:n;cout请分别输入物品的重量:endl;for(i=0;iwi;cout请分别输入物品的体积:endl;for(i=0;izi;cout请分别输入物品的价值:e
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

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

最新文档

评论

0/150

提交评论