求解背包问题_第1页
求解背包问题_第2页
求解背包问题_第3页
求解背包问题_第4页
求解背包问题_第5页
全文预览已结束

下载本文档

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

文档简介

1、一.题目求解背包问题，给出动态规划算法，并完成以下要求：a、对于下边背包问题的实例，应用自底向上动态规划算法求解。物品重量价值13252220311544405550已知：背包承重W=6b、a中的实例有多少个不同的最优子集？c、一般来说，如何从动态规划算法所生成的表中判断出背包问题的实例是不是具有不 止一个最优子集？二.解题思路(主要难点或关键点)阶段划分用动态规划算法解决问题，首先是要找到解决问题的阶段。设第k件物品的重量为wi,背包的总容量为m，在不考虑其他物品情况下:若当前背包容量为0 wi-1，则一定不能选取第i件物品；若当前背包容量为wim，就有可能选取第i件物品。结构设计设一个存储

2、动态规划过程的二维数组cim共有0n行，0m列。行下表代表 0n件物品，列下标代表当前背包容量。元素中存储的是当前阶段可能的最大获利值。状态转移解决过程从第n件物品开始，j代表当前背包容量：cij=0，j=0,1,2, ,，wi-1cij= pn，j= wi，wi+1，wi+2, ，m现在开始第二阶段，解决第n-1件物品的取舍可能，及当前的获利情况。分下面 几种情况进行讨论。当前背包容量jwi-1时，可以选取第i-1件物品，也可以不选第i-1件物品。若选取第i-1件物品，则对于其前面阶段物品的获利值，就只能考虑容量为 j-wi-1的情况，这时： TOC o 1-5 h z ci-1j= cij

3、- wi-1+ pi-1，j= wi-1，wi-1+1，m若不选取第i-1件物品，则获利与上一阶段相同：ci-1j= cij，j= wi-1，wi-1+1，m要获取最大获利，自然要取这两种获利中最大的一个，即：ci-1j=maxcij-wi-1+pi-1，cij，(j=wi-1，wi-1+1，m)以上每个阶段都和第二阶段一样，由上一阶段的可能获利情况，递推出本阶 段的结论.301520354045604015203540(2)5560(2)50152035405565四.算法效率分析(时间、空间)岸时间效率O (n*m)r=五，实验过程算法具体实现#includeintc67;intknapsack(int m,int n)int i,j,w5,p5;for(i=1;i=n;i+)scanf(n%d,%d”,&wi,&pi);for(i=0;i6;i+)for(j=0;j7;j+)cij=0;for(i=1;i=n;i+)for(j=1;j=m;j+)if(wici-1j)cij=pi+ci-1j-wi;else cij=ci-1j;else cij=ci-1j;return(cnm);int main()int m,n;int i,j;scanf(%d,%d”,&m,&n);printf(%d”,knapsack(m,n);printf(n);f

人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

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

最新文档

评论

0/150

提交评论