利用动态规划解决01背包问题

《利用动态规划解决01背包问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、l总第286期叠■—圆■_圆■_llJ利用动态规划解决01背包问题孙宇兴谭芬(中国人民解放军通信指挥学院湖北武汉430010)【摘要】在计算机越来越普及的今天，人们对计算机的求知欲日渐增长，对计算速度的要求也越来越高，因此算法也越来越受人重视，好的算法可以加快计算速度和减少系统资源。动态规范是算法里一种非常重要的方法，是求解决策过程最优化的数学方法。动态规划自问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其他方法求解更为方便

2、。本文通过对经典的01背包问题的求解，从动态规划的角度进行阐述，通过案例对该算法的计算过程进行了直观的描述，并对该算法进行了一定的优化，最后指出该算法的优缺点。【关键词】背包动态规划时间复杂度空间复杂度【中图分类号】TP51[文献标识码】A[文章编号】1009-5549(2010)05—0121一O5前言算，节省时间。我们可以用一个表来记录所有已解的子问题背包问题是一个经典的动态规划模型，很多关于算法的的答案。不管该子问题以后是否被用到，只要它被计算过，教材都把它作为一道例题，该问题既简单又容易理解，而且就将其结果填入表中，这就是

3、动态规划法的基本思路。具体在某种程度上还能够揭示动态规划的本质。的动态规划算法多种多样，但它们具有相同的填表格式。将具有不同重量和价值的物体装入一个有固定载重量的(二)算法设计背包，以获取最大价值，这类问题被称为背包问题。假定背包的载重量范围为O～m。类似于资源分配那样，背包问题可以扩展出很多种问题，而01背包问题是最常令optp(j)表示在前i个物体中，能够装入载重量为J的背包见、最有代表性的背包问题。所得的最大价值，j=l，2，⋯⋯，m。显然，此时在前i个物一体中，有些物体可以装入背包，有些物体不能装入背包。于、问题描述给定一

4、个载重量为M的背包及r1个物体，物体i的重量为是，可以得到下面的动态规划函数：W、价值为P，1≤i≤n，要求把这些物体装入背包，使背(0)=o()=0(4)包内的物体价值总量最大。此处我们讨论的物体是不可分割。⋯p．(⋯，)：』【optp¨()_，<(5)的，通常称这种物体不可分割的背包问题为0l背包问题。max{optpf-l()，optpf．】(一)+)J(6)二、基本思路(4)式表明：把前面i个物体装入载重量为0的背包，或01背包问题的特点是：每种物体只有一件，可以选择放者把0个物体装入载重量为J的背包，得到的价值都为0。(

5、5)或者不放。假设：x表示物体i被装入背包的情况，xi：0，式表明：当第i个物体的重量大于背包的载重量时，装入前1。当X：O时，表示物体没有被装入背包；当X=l时，表示物i个物体得到的最大价值，与装入前i-1个物体得到的最大体被装入背包。根据问题的要求，有如下的约束方程(1)和价值一样，即第i个物体没有装入背包。(6)式表明：当第i目标函数(2)：个物体的重量小于背包的载重量时，如果第i个物体装入背包，背包中物体的价值，等于把前i-1个物体装入载重量为∑wixi≤M(1)i=lj-w的背包所得到的价值与第i个物体的价值P之和；如果

6、第optp=maxx矽pi量xi(2)】i个物体没有装入背包，则背包中物体的价值，等于把前i-1i=1个物体装入载重量为j的背包，却不装入第i个物体所取得的于是，该问题归结为寻找一个满足上述约束方程，并使价值。显然，这两种装入方法，在背包中所取得的价值不一目标函数达到最大的解向量：X=，X，，L，．)(3)的问题。定相同，因此，取这两者中的最大值，作为把前面i个物体三、利用动态规划法求解01背包问题装入载重量为j的背包所取得的最优价值。(一)动态规划算法的基本思想该算法可分为n阶段：动态规划算法通常用于求解具有某种最优性质的问题。

7、第一阶段，只装入一个物体，计算在不同载重量的背包在这类问题中，可能会有许多可行解。每一个解都对应于情况下，所取得的最大价值；一个值，我们希望找到具有最优值的解。动态规划算法与分第二阶段，装入前两个物体，按(5)式和(6)式计算在不治法类似，其基本思想也是将待求解问题分解成若干个子同载重量的背包情况下，取得的最大价值；问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经第n阶段，装入前n个物体，按(5)式和(6)式计算在不同分解得到子问题往往不是互相独立的。若用分治法来解这类载重量

8、的背包情况下，取得的最大价值，而在背包载重量为问题，则分解得到的子问题数目太多，有些子问题被重复计M时，所得结果就是我们想要的结果。算很多次。如果我们能够保存已解决的予问题的答案，而在为了确定具体哪个物体装入背包，从optp(m)的值向前需要时再找