浅谈计算机中背包问题的动态规划解法

摘要：背包问题和动态规划问题是计算机专业学生算法学习中的重点。本文介绍了背包问题和动态规划的基本概念，然后通过实例详细的论述了背包型动态规划的实现过程。

关键词：0-1背包；动态规划；背包型动态规划1什么是背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。大致求解的问题类型：给定N件物品，每件物品都有自己的体积和价值，在背包总体积一定的情况下，我们如何选择，才能使得背包内物品的总价值最高。它是在1978年由Merkel和Hellman提出的。与此相类似的问题常出现在商业、组合数学、计算复杂性理论、密码学和应用数学等领域中。

2什么是动态规划

动态规划(dynamic programming)是运筹学的一个分支，它是解决多阶段决策过程的最优化的数学方法。20世纪50年代初美国数学家贝尔曼(R.E.Bellman)等人在研究多阶段决策过程(multistep decision process)的优化问题时，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作

3什么是背包问题的动态规划解法

所谓背包问题的动态规划解法其实也就是运用动态规划的思想快速、高效的求得背包问题的最优解的一种解题方式。我们知道对于背包问题：对于任何一件物品，我们都可以选择往背包里放或者不放；而解决动态规划的最核心一点：就是必须求得问题的状态转移方程！背包问题的选择放或者不放这两种决策方式恰恰会导致两种不同的状态，完全符合动态规划所能解决的类型。

4举例说明背包型动态规划的具体过程

例如：从前有一个地主老财，他的家乡发生了战乱，为了躲避这场战乱，他决定带领全家人搬迁到一个没有战乱的地方，所以他准备了一个大箱子，想把家里的值钱的东西都带走，可是家里的东西太多了，根本不能完全带走，所以他想让他的管家帮他一下，告诉他应该装哪些东西，才能使带走的东西总价值最大，并告诉他总价值是多少。下面会给出箱子的总体积V和物品的件数N，以及每件物品的体积v和价值c；任何一件物品都不可分割，因为物品一旦分割便一文不值。为了既能说明问题，又能够使描述的最简洁，我们把数值都定义的小一些！假设箱子的总体积为10，物品的件数为5；接下来的5件物品的体积和价值分别为：第一件：体积为8 价值为2；第二件：体积为4 价值为5；第三件：体积为3 价值为5；第四件：体积为4 价值为3；第五件：体积为2价值为2。

解题思路：首先我们初始化11个箱子，表示箱子可能会出现的11种状态：如dp[0]=0表示背包内物体所占用的体积为0时，背包内物品的总价值0；dp[1]=0表示背包内物体所占用的体积为1时，背包内物品的总价值0；••••••；dp[10]=0 表示背包内物体所占用的体积为10时，背包内物品的总价值0。接下来我们来看第一组数组：体积8 价值2，我们考虑一下如果把该物品装进箱子，箱子中物品占用的体积会达到多少呢？很明显，箱子内的物品占用的体积有可能是8体积，9体积，10体积。因为如果箱子原先是空的，那么把该物品放进去后，所有物品占用的总体积为8；如果箱子原先已经放了1体积物品了，那么把该物品放进去后，所有物品占用的总体积为9；如果箱子原先已经放了2体积物品了，那么把该物品放进去后，所有物品占用的总体积为10；如果箱子原先已经放了3体积物品了，8+3=11，大于箱子的总体积，放不下！这是考虑到把物品放进箱子里，那么什么时候我们不把物品放进箱子里呢？还以上面的数据为例：如果把这件物品放进去，达到8体积的状态，价值为dp[0]+2，那么我们用dp[8]和dp[0]+2比较，如果dp[8]

列号0,1,2,3......10表示箱子中物品占用的总体积；行号0,1,2,3,4,5表示第i=0,1,2,3,4,5件物品可放入箱子中的情况下，箱子中物品的最大价值。

很明显，箱子中放入物品后，总的最大价值为12。

综上所述，背包型动态规划是算法中的经典问题之一，也是ACM国际大学生程序设计竞赛中的高频考点。由于竞赛中试题对该算法的考察比较灵活，因此必须深入学习该算法的思想，熟练掌握该算法的原理，才能在赛场上取得胜利，也才能在实际生活中得到广泛应用。

[参考文献]

[1]田烽楠,王于.求解0-1背包问题算法综述.软件导刊，2009,8(1):59-61.

[2]马,朱刚,宁爱兵.蚁群优化算法.北京:科学出版社，2010.

[3]崔逊学.多目标进化算法及其应用.北京:国防工业出版社，2008.

[4]于惠.遗传算法的改进研究及在背包问题中的应用.山东师范大学硕士论文，2009.