算法分析及复杂性理论实验报告背包问题

上传人:第*** 文档编号:61734780 上传时间:2018-12-11 格式:DOCX 页数:17 大小:1.12MB
返回 下载 相关 举报
算法分析及复杂性理论实验报告背包问题_第1页
第1页 / 共17页
算法分析及复杂性理论实验报告背包问题_第2页
第2页 / 共17页
算法分析及复杂性理论实验报告背包问题_第3页
第3页 / 共17页
算法分析及复杂性理论实验报告背包问题_第4页
第4页 / 共17页
算法分析及复杂性理论实验报告背包问题_第5页
第5页 / 共17页
点击查看更多>>
资源描述

《算法分析及复杂性理论实验报告背包问题》由会员分享,可在线阅读,更多相关《算法分析及复杂性理论实验报告背包问题(17页珍藏版)》请在金锄头文库上搜索。

1、深 圳 大 学 实 验 报 告课程名称: 算法分析与复杂性理论 实验名称: 实验四 动态规划 学院: 计算机与软件学院 专业: 软件工程 报告人: 文成 学号: 2150230509 班级: 学术型 同组人: 无 指导教师: 杨烜 实验时间: 2015/11/52015/11/18 实验报告提交时间: 2015/11/18 教务处制一 实验目的与实验内容实验目的:(1)掌握动态规划算法设计思想。(2)掌握背包问题的动态规划解法。实验内容:1. 编写背包问题的动态规划求解代码。2背包容量为W,物品个数为n,随机产生n个物品的体积(物品的体积不可大于W)与价值,求解该实例的最优解。3.分别针对以下

2、情况求解第一组:(n=10,W=10),(n=10,W=20),(n=10,W=30)第二组:(n=20,W=10),(n=20,W=20),(n=20,W=30)第三组:(n=30,W=10),(n=30,W=20),(n=30,W=30)4.画出三组实验的时间效率的折线图,其中x轴是W的值,y轴是所花费的时间,用不同的颜色表示不同n所花费的时间。二实验步骤与结果背包问题的问题描述:给定n种物品和一个背包。物品i的重量是,其价值为,背包容量为C。问应该如何选择装入背包的物品,使得装入背包中物品的总价值最大?背包问题的算法思想:考虑一个由前i个物品(1=i=n)定义的实例,物品的重量分别为w1

3、,w2、价值分别为v1,vi,背包的承重量为j(1=j=0),最优子集是由该物品和前i-1个物品中能够放进承重量为j-wi的背包的最优子集组成。这种最优子集的总价值等于vi+Vi-1,j-wi。因此,在前i个物品中最优解得总价值等于这两个价值中的最大值。当然,如果第i个物品不能放进背包,从前i个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。这个结果导致了下面的这个递推关系式:初始条件:当i,j0时,V为了计算第i行第j列的单元格i,j,我们拿前一行同一列的单元格与vi加上前一行左边wi列的单元格的和做比较,计算出两者的较大值。相关代码;void knapsack(i

4、nt v, int w, int* m, int c, int n)/求最优值 int jmax = min(wn-1, c); for (int j = 0; j = jmax; j+) mnj = 0; for (int jj = wn; jj 1; i-)/递归部分 jmax = min(wi-1, c); for(int j = 0; j = jmax; j+) mij = mi+1j; for(int jj = wi; jj = w1) m1c = max(m1c, m2c-w1+v1); cout endl 最优值: m1c endl; coutendl; coutendl; in

5、t traceback(int x, int w, int* m, int c, int n) /求最优解 coutendl得到的一组最优解如下: endl; for(int i = 1; i n; i+) if(mic = mi+1c)xi = 0; else xi = 1; c -= wi; xn = (mnc) ? 1:0; for(int y = 1; y = n; y+) cout xy t; cout endl;return xn; 用课本上的一个例子进行测试:预期结果应该是物品1,2和4。价值为37美元。背包问题中,对于一个物品,只有放入背包和不放入背包两种状态,用0表示物品不放

6、入背包,用1表示放入背包。上图的结果显示最优值为37,物品一、二、四放入包中,与预期结果相同。随机产生n个物品的重量与价值,求解该实例的最优解。产生随机数的代码如下:调用以上两个方法求解对n=20,w=20做测试Vi和wi都是随机产生的,正确地得到了结果。注:(1) 为了保证不使用特殊数字,采用随机生成数组的方法。for(int i=0;in;i+)ai=rand()%10;bi=rand()%10;为了保证每次得到的数字不同,必须使用种子,给不同的初始值srand(unsigned)time(NULL);(2) 用取系统时间的方法,来获取该算法的时间。由于time只能取到毫秒级别,当算法的时

7、间太小时,用多次执行算法的方法来获取算法执行时间time_t time1,time2; time1=time(NULL); for(i=0;i100;i+)/time2=time(NULL);cout(time2-time1)/100endl;三实验分析分别针对以下情况求解:(先展示结果,时间太短,运行时间显示为零,稍后再做处理)第一组:(n=10,W=10),(n=10,W=20),(n=10,W=30)第二组:(n=20,W=10),(n=20,W=20),(n=20,W=30)第三组:(n=30,W=10),(n=30,W=20),(n=30,W=30)用取系统时间的方法,来获取该算法的

8、时间。由于time只能取到毫秒级别,当算法的时间太小时,用多次执行算法的方法来获取算法执行时间time_t time1,time2; time1=time(NULL); for(i=0;i1000000;i+)/time2=time(NULL);cout(time2-time1)/100000endl;如图所示,统计的时间为运行1000000次数后的时间以上统计的时间为运行1000000次数后的时间毫秒n=10n=20n=30w=100.00010.00020.0004w=200.00020.00040.0005w=300.00020.00050.0008三组实验的时间效率的折线图,其中x轴是

9、W的值,y轴是所花费的时间,用不同的颜色表示不同n所花费的时间。结论:可以发现n的规模越大,所花费的时间越多。当n固定时,花费时间随着w的增大而增大。但n的影响力是最大的。因为动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题, 采用顺序求解方法, 通过解一系列小问题达到求解整个问题目的。所以分解的小问题的规模,直接决定了算法的效率。四实验心得本次实验虽然花费很大的心思,但确实让我动态规划的认识更加深刻。动态规划没有准确的数学表达式和定义精确的算法,它强调具体问题具体分析。这次实验结束后让我感觉到好的算法是多么的重要,当然合理利用算法也是不可忽视的。这次实验虽然花了很大精力,却收获累累。 指导教师批阅意见:成绩评定: 指导教师签字: 年 月 日备注:注:1、报告内的项目或内容设置,可根据实际情况加以调整和补充。 2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 办公文档 > 解决方案

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号