内容发布更新时间 : 2024/10/18 7:53:58星期一 下面是文章的全部内容请认真阅读。

精品文档

湖南理工学院课程论文

课程名称 数据结构与算法设计 姓 名 学 号 专业班级 年 级 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. 问题描述·······························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被装入背包。假设有五个物品，其重量分别是{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个物品是否被装入背包中为止。

精品文档