0-1背包问题

学 院 计算机科学技术学院 专业班级 年 级 学 号 姓 名 xxx 日 期 xxxx年xx月xx日

目录 摘要 1 引言 1

摘要 算法是一个系列解决问题的清晰指令,即在有限时间内能够对一定规范的输入,能够得到所需要的输出。如果一个算法本身是有缺陷的!那么他往往不是这个问题的最佳解决方法,可见一个算法的优劣是通过一定的准则来规定的。通过这学期的对《计算机算法分析设计》这门课程的学习让我们充分的了解到了计算机算法的多样性和复杂性，让我们更加细心和耐心的去对待这门课程。例如甲某要去某个地方旅游,他有很多种方案到旅游地,但是不见的每种方案都是合理最优的!这时就是需要考虑透过一定的算法来得到自己的最优路线。所以可见算法就是以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件，必须遵循软件工程的原则，设计出高效率的程序。一个高效的程序不仅需要编程技巧，更需要合理的数据组织和清晰高效的算法。

引言 对于计算机科学来说，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 一个算法应该具有以下五个重要的特征： 有穷性：一个算法必须保证执行有限步之后结束； 确切性：算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。

1.问题描述 给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包容量为C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分。问：如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 2.算法设计与分析 2.1算法分析 在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个物品是否被装入背包中为止。 2.2算法设计 设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