算法设计与分析课程设计报告
更新时间:2023-12-14 13:35:01 阅读量: 教育文库 文档下载
湖南理工学院课程论文
课程名称 数据结构与算法设计 姓 名 学 号
专业班级 年 级 2014级
学 院 计算机学院 日 期 2015年6月25日
课程论文评价标准
评价等级(分值) 指标 评价内容 A 选题 选题是否新颖;是否有意义;是否与本门课程相关。 论文题目 0-1背包问题的设计与实现
得分 B C D 5-0 20-16 15-11 10-6 思路是否清晰;逻辑是否严密;结构论证 是否严谨;研究方法是否得当;论证是否充分。 20-16 15-11 10-6 5-0 文献 文献资料是否翔实;是否具有代表性。 20-16 15-11 10-6 规范 能力 文字表达是否准确、流畅;是否符合学术道德规范。 是否运用了本门课程的有关理论知识;是否体现了科学研究能力。 20-16 15-11 10-6 20-16 15-11 10-6 总分: 5-0 5-0 5-0 评阅教师签名: 年 月 日 1
目录
1. 问题描述·······························3 2. 算法设计分析···························3 3. 程序编码与调试分析·····················5 4. 测试结果·······························7 5. 自学知识·······························7 6. 课程设计心得体会·······················8 7. 参考文献·······························8
2
1.问题描述
给定n种物品和一个背包,物品i的重量是wi,其价值为vi,背包容量为C。在选择装入背包的物品时,对每种物品i只有两种选择:装入背包或不装入背包,即不能将物品i装入背包多次,也不能只装入物品i的一部分。问:如何选择装入背包的物品,使得装入背包中物品的总价值最大?
2.算法设计与分析 算法分析
在0-1背包问题中,物体被装入一个背包,或者不被装入背包,设xi表示物
品i装入背包的情况,则当xi=0时,表示物品i没有被装入背包,xi=1时,表示物品i被装入背包。假设有五个物品,其重量分别是{2,2,6,5,4},价值分别是{6,3,5,4,6},背包的容量为10。根据动态规划函数,用一个(n+1)×(C+1)的二维表V,V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。
按下述方法来划分阶段:第一阶段,只装入前1个物品,确定在各种情况下的背包能够得到的最大价值;第二阶段,只装入前2个物品,确定在各种情况下的背包能够得到的最大价值;依此类推,直到第n个阶段。最后,V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。
为了确定装入背包的具体物品,从V(n,C)的值向前推,如果V(n,C)>V(n-1,C),表明第n个物品被装入背包,前n-1个物品被装入容量为C-wn的背包中;否则,第n个物品没有被装入背包,前n-1个物品被装入容量为C的背包中。依此类推,直到确定第1个物品是否被装入背包中为止。
3
算法设计
设n个物品的重量存储在数组w[n]中,价值存储在数组v[n]中,背包容量为C,数组V[n+1][C+1]存放迭代结果,其中V[i][j]表示前i个物品装入容量为j的背包中获得的最大价值,数组x[n]存储装入背包的物品,动态规划法求解0/1背包问题的算法如下:
int KnapSack(int n, int w[ ], int v[ ]) {
for (i=0; i<=n; i++) //初始化第0列 V[i][0]=0;
for (j=0; j<=C; j++) //初始化第0行 V[0][j]=0;
for (i=1; i<=n; i++) //计算第i行,进行第i次迭代 for (j=1; j<=C; j++)
if (j
else x[i]=0; }
return V[n][C]; //返回背包取得的最大价值 }
4
3.程序编码与调试分析
程序编码 #include
int KnapSack(int n,int C,int *w,int *v,int V[][11]) { int i,j,x[i];
for (i=0;i<=n;i++) //初始化第0列
V[i][0]=0;
for (j=0;j<=C;j++) //初始化第0行
V[0][j]=0;
for (i=1;i<=n;i++) //计算第i行,进行第i次迭代 for (j=1;j<=C;j++)
if (j V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j], V[i-1][j-w[i]]+v[i]); j=C; //求装入背包的物品 for (i=n; i>0; i--){ } 5 if (V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; for(i=0;i<=n;i++) {for(j=0;j<=C;j++) printf(\ \ } printf(\背包取得的最大价值:\ } int main(){ int n=5,C=10,i; int V[6][11]; int w[6],v[6]; for(i=1;i<6;i++) scanf(\ for(i=1;i<6;i++) scanf(\ KnapSack(5,10,w,v,V); } 调试分析 以上0-1背包问题的代码的时间复杂度为O(nc).(n表示物品的总数,c为重量限制背包容量),当背包容量c很大时,算法需要的计算时间比较多。动态规划依赖于上一个或者上一行的解,所以我常在输出子序列的时候出现问题,这源自于对动态规划的知识不是很了解。 printf(\ //返回背包取得的最大价值 printf(\ 6 4.测试结果 5.自学知识 在这个程序设计中,涉及了动态规划,动态规划是解决多阶段决策问题常用的最优化理论,其基本思想是沿着决策的阶段划分自问题,决策的阶段可以随时间划分,也可以随着问题的转换状态划分。 设计动态规划算法,通常可按照以下几个步骤进行: (1)找出最优解的性质,并刻画其结构特征。 (2)递归地定义最优解的值。 (3)以自底而上的方式计算出最优值。 7 (4)根据计算最优值时得到的信息,构造一个最优解。 6.课程设计心得体会 动态规划依赖于上一个或上一行的解,这次实验总是在输出子序列的时候出现问题,本来动态规划的知识没有学好,正好在最后的课程设计选0-1背包问题作为实验对象,完完整整的通过这次设计对0-1背包问题和动态规划都有了很深刻的了解,这有助于以后我们在实际问题中解决一些复杂性较大的问题,提高程序的运行效率。 7.参考文献 [1] 谭浩强等. 《C语言程序社会》,清华大学出版社,2013. [2] 王晓华等. 《算法的乐趣》, 人民邮电出版社, 2015. 8
正在阅读:
算法设计与分析课程设计报告12-14
皮肤试验诊断和脱敏治疗的注意事项06-03
第5课 《伤仲永》教案08-12
天津市部分区县2019-2020学年第一学期四年级语文(部编版)期末真题卷(图片版 含答案)05-03
省情、市情07-08
2012年10月自考线性代数真题与答案07-17
高级社会体育指导员公共理论考核试题308-07
作业5 第三章 合伙企业法 习题12-01
_华龙一号_中国先进压水堆核电机组_03-18
人力资源会计信息披露的现状及对策11-10
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 设计
- 算法
- 课程
- 报告
- 分析
- 关工委各项工作制度
- 实验七 - matlab求解级数有关计算
- 2018成本会计工作总结及2019年工作计划
- 小学语文词语练习
- 新课改数学高考题型解析
- 2019高考总复习优化设计1轮文科数学人教A课时规范练43 直线与圆、圆与圆的位置关系(附答案)
- 杭州市人民政府办公厅关于外商及外地来杭投资项目引荐者奖励有关
- 实验四 利用EXCEL软件进行直线回归与相关分析(2)
- 直流电机-习题
- PL0源程序-编译原理实验代码
- 产业组织理论复习资料要点
- 高中物理必修(一)第一章 运动的描述 知识点总结
- 设计分频器实现:输入时钟频率为50MHZ,输出400HZ、100HZ、25HZ、1HZ时钟
- 三年级下-Module3-Unit3-A
- 商业银行会计内部控制制度存在的问题及对策
- 中国于氏家谱珍藏目录
- 小数点移动教学反思
- 中国密封圈市场评估报告目录
- 2018-2019学年高中语文 第2单元 6 逍遥游教师用书 新人教版必修5
- 小学四年级下册单词测试