算法设计与分析课程设计报告-背包问题的设计与实现.docx

湖南理工学院课程论文论文题目 0-1背包问题的设计与实现 课程名称 数据结构与算法设计 姓 名 学 号 专业班级 年 级 2014级 学 院 计算机学院 日 期 2015年6月25日 课程论文评价标准指标评价内容评价等级（分值）得分ABCD选题选题是否新颖；是否有意义；是否与本门课程相关。20-1615-1110-65-0论证思路是否清晰；逻辑是否严密；结构是否严谨；研究方法是否得当；论证是否充分。20-1615-1110-65-0文献文献资料是否翔实；是否具有代表性。20-1615-1110-65-0规范文字表达是否准确、流畅；是否符合学术道德规范。20-1615-1110-65-0能力是否运用了本门课程的有关理论知识；是否体现了科学研究能力。20-1615-1110-65-0 评阅教师签名： 年 月 日 总分：目录1. 问题描述32. 算法设计分析33. 程序编码与调试分析54. 测试结果75. 自学知识76. 课程设计心得体会87. 参考文献81. 问题描述给定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，Vij表示把前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个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：int KnapSack(int n, int w , int v ) for (i=0; i=n; i+) /初始化第0列 Vi0=0; for (j=0; j=C; j+) /初始化第0行 V0j=0; for (i=1; i=n; i+) /计算第i行，进行第i次迭代 for (j=1; j=C; j+) if (j0; i-) if (VijVi-1j) xi=1; j=j-wi; else xi=0; return VnC; /返回背包取得的最大价值3. 程序编码与调试分析程序编码#include #include int max(int x,int y) if(x=y) return x; else return y; int KnapSack(int n,int C,int *w,int *v,int V11) int i,j,xi; for (i=0;i=n;i+) /初始化第0列 Vi0=0; for (j=0;j=C;j+) /初始化第0行 V0j=0; for (i=1;i=n;i+) /计算第i行，进行第i次迭代 for (j=1;j=C;j+) if (j0; i-) if (VijVi-1j) xi=1; j=j-wi; else xi=0; for(i=0;i=n;i+)for(j=0;j=C;j+) printf(%3d ,Vij); printf(n); printf(背包取得的最大价值:); printf(%d,VnC); /返回背包取得的最大价值 int main() int n=5,C=10,i; int V611; int w6,v6; for(i=1;i6;i+) scanf(%d,&wi); for(i=1;i6;i+) scanf(%d,&vi); KnapSack(5,10,w,v,V); 调试分析以上0-1背包问题的代码的时间复杂度为O(nc).（n表示物品的总数，c为重量限制背包容量），当背包容量c很大时，算法需要的计算时间比较多。动态规划依赖于上一个或者上一行的解，所以我常在输出子序列的时候出现问题，这源自于对动态规划的知识不是很了解。4. 测试结果5. 自学知识在这个程序设计中，涉及了动态规划，动态规划是解决多阶段决策问题常用的最优化理论，其基本思想是沿着决策的阶段划分自问题，决策的阶段可以随时间划分，也可以随着问题的转换状态划分。设计动态规划算法，通常可按照以下几个步骤进行：（1） 找出最优解的性质，并刻画其结构特征。（2） 递归地定义最优解的值。（3） 以自底而上的方式计算出最优值。（4） 根据计算最优值时得到的信息，构造一个最优解。6. 课程设计心得体会动态规划依赖于上一个或上一行的解，这次实验总是在输出子序列的时候出现问题，本来动态规划的知识没有学好，正好在最后的课程设计选0-1背包问题作为实验对象，完完整整的通过这次设计对0