湖南理工学院课程**。
**题目 0-1背包问题的设计与实现。
课程名称数据结构与算法设计。
姓名学号 专业班级年级 2014级
学院计算机学院日期 2023年6月25日
课程**评价标准。
目录。1. 问题描述3
2. 算法设计分析3
3. 程序编码与调试分析5
4. 测试结果7
5. 自学知识7
6. 课程设计心得体会8
7. 参考文献8
1.问题描述。
给定n种物品和一个背包,物品i的重量是wi,其价值为vi,背包容量为c。在选择装入背包的物品时,对每种物品i只有两种选择:装入背包或不装入背包,即不能将物品i装入背包多次,也不能只装入物品i的一部分。
问:如何选择装入背包的物品,使得装入背包中物品的总价值最大?
2.算法设计与分析。
算法分析。在0-1背包问题中,物体被装入一个背包,或者不被装入背包,设xi表示物品i装入背包的情况,则当xi=0时,表示物品i没有被装入背包,xi=1时,表示物品i被装入背包。假设有五个物品,其重量分别是,价值分别是,背包的容量为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个物品是否被装入背包中为止。
算法设计。设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 (jelse v[i][j]=max(v[i-1][j], v[i-1][j-w[i]]+v[i]);
j=c; /求装入背包的物品。
for (i=n; i>0; i--)
return v[n][c]; 返回背包取得的最大价值。
3.程序编码与调试分析。
程序编码。#include<>
#include<>
int max(int x,int y)
for(i=0;i<=n;i++)
for(j=0;j<=c;j++)
printf("%3d ",v[i][j]);
printf("");
printf("背包取得的最大价值:")
printf("%d",v[n][c]);返回背包取得的最大价值
int main(){
int n=5,c=10,i;
int v[6][11];
int w[6],v[6];
for(i=1;i<6;i++)
scanf("%d",&w[i]);
for(i=1;i<6;i++)
scanf("%d",&v[i]);
knapsack(5,10,w,v,v);
调试分析。以上0-1背包问题的**的时间复杂度为o(nc).(n表示物品的总数,c为重量限制背包容量),当背包容量c很大时,算法需要的计算时间比较多。
动态规划依赖于上一个或者上一行的解,所以我常在输出子序列的时候出现问题,这源自于对动态规划的知识不是很了解。
4.测试结果。
5.自学知识。
在这个程序设计中,涉及了动态规划,动态规划是解决多阶段决策问题常用的最优化理论,其基本思想是沿着决策的阶段划分自问题,决策的阶段可以随时间划分,也可以随着问题的转换状态划分。
设计动态规划算法,通常可按照以下几个步骤进行:
1)找出最优解的性质,并刻画其结构特征。
2)递归地定义最优解的值。
3)以自底而上的方式计算出最优值。
4)根据计算最优值时得到的信息,构造一个最优解。
6.课程设计心得体会。
动态规划依赖于上一个或上一行的解,这次实验总是在输出子序列的时候出现问题,本来动态规划的知识没有学好,正好在最后的课程设计选0-1背包问题作为实验对象,完完整整的通过这次设计对0-1背包问题和动态规划都有了很深刻的了解,这有助于以后我们在实际问题中解决一些复杂性较大的问题,提高程序的运行效率。
7.参考文献。
1] 谭浩强等。 《c语言程序社会》,清华大学出版社,2013.
2] 王晓华等。 《算法的乐趣》, 人民邮电出版社, 2015.
算法设计与分析课程设计报告
湖南理工学院课程 题目 0 1背包问题的设计与实现。课程名称数据结构与算法设计。姓名学号。专业班级年级 2014级。学院计算机学院日期 2015年6月25日。课程 评价标准。目录。1.问题描述3 2.算法设计分析3 3.程序编码与调试分析5 4.测试结果7 5.自学知识7 6.课程设计心得体会8 7...
算法分析与设计课程设计报告
算法分析与设计。课程设计报告 课程名称算法分析与设计。实验学期 2013 年至 2014 年第 1 学期。所在学院理学院年级 2011 专业班级信息与计算科学3班 学生姓名郑松辉学号 201130760334 自评成绩 96 教师评成绩 指导教师赵峰 算法分析与设计 课程设计报告。目录。1课程实验概...
算法设计与分析课程设计报告
算法与分析。课程设计报告。题目 算法设计和分析 专业 网络工程 班级 1020552 学号 11 姓名 赫前进 太原工业学院计算机工程系。2012年 11月 24 日。第二章主元素问题。一 算法问题描述。主元素问题 设t 0.n 1 是n个元素的数组。对任一元素x,设s x 当 s x n 2时,称...