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