动态规划中的0-1背包模型

0-1背包动态规划解决问题

一、问题描述：

有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

二、总体思路：

根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。

三、动态规划的原理及过程：

number＝4，capacity＝7

i 1 2 3 4

w(重量) 3 5 2 1

v(价值) 9 10 7 4

原理：

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

过程：

a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积（重量）；

b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；

c) 约束条件，W1X1+W2X2+…+WnXn

d) 定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；

e) 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理，采用反证法证明：

假设(X1，X2，…，Xn)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解， 假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1；

第２９卷第１期　２　０　１　２年３月　经　济　数　学　ＪＯＵＲＮＡＬ　ＯＦ　ＱＵＡＮＴＩＴＡＴＩＶＥ　ＥＣＯＮＯＭＩＣＳ　ＶｏｌＪ　２９。Ｎ０．１　Ｍａｒ．２　Ｏ　１　２　

一种求解分组０—１背包问题的动态规划法　

蒋亚军　，易学军。　

（１．湖南科技学院计算机与通信工程系，湖南永州４２５１００；　２．湖南大学数学与计量经济学院，湖南长沙４１００８２）　

摘要研究了分组Ｏ一１背包问题，提出了一种动态规划解决方法，在物品总数为　个和背包承重　量为Ｗ时，递推过程的复杂度为Ｏ（ｎＷ），回溯过程的复杂度为０（　）．计算实例表明利用该方法易于找到　最优解．　关键词　背包问题；ＮＰ完全；动态规划　中图分类号ＴＰ３０１　文献标识码Ａ　

Ａ　Ｄｙｎａｍｉｃ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｍｅｔｈｏｄ　ｆｏｒ　

Ｃｌａｓｓｉｆｉｅｄ　０—１　Ｋｎａｐｓａｃｋ　Ｐｒｏｂｌｅｍ　

ＪＩＡＮＧ　Ｙａ－ｊｕｎ　，ＹＩ　Ｘｕｅ－ｊｕｎ。　

（１．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒ　ａｎｄＣｏｍｍｕｎｉｃａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ。ＨｕｎａｎＵｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄＥｎｇｉｎｅｅｒｉｎｇ。Ｙｏｎｇｚｈｏｕ，　Ｈｕｎａｎ　４２５１００　Ｃｈｉｎａ；２．Ｃｏｌｌｅｇｅ　ｏｆＭａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｅｃｏｎｏｍｅｔｒｉｃｓ，Ｈｕｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ。Ｃｔｍｎｇｓｈａ，Ｈｕｎａｎ　４１００８２　Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ　Ｔｈｉｓ　ｐａｐｅｒ　ｓｔｕｄｉｅｄ　ｔｈｅ　ｃｌａｓｓｉｆｉｅｄ　Ｏ－－１　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ，ａｎｄ　ｐｒｏｐｏｓｅｄ　ａ　ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｍｅｔｈｏｄ．Ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｅ　ｒｅｃｕｒｓｉｖｅ　ｐｒｏｃｅｓｓ　ｉｓ　Ｏ（ｎＷ），ａｎｄ　ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｅ　ｔｒａｃｅｂａｃｋ　ｐｒｏｃｅｓｓ　ｉｓ　ｏ（　），ｗｈｅｒｅ　ｎ　ｉｓ　ｔｈｅ　ｔｏｔａｌ　ｎｕｍｂｅｒ　ｏｆ　ｇｏｏｄｓ　ａｎｄ　Ｗ　ｉｓ　ｔｈｅ　ｂｅａｒｉｎｇ　ｗｅｉｇｈｔ　ｏｆ　ｔｈｅ　ｋｎａｐｓａｃｋ．Ｔｈｅ　ｅｘａｍｐｌｅ　ｓｈｏｗｓ　ｔｈａｔ　ｉｔ　ｉｓ　ｅａｓｙ　ｔＯ　ｆｉｎｄ　ｔｈｅ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｂｙ　ｔｈｅ　ｍｅｔｈｏｄ．　Ｋｅｙ　ｗｏｒｄｓ　Ｋｎａｐｓａｃｋ　Ｐｒｏｂｌｅｍ；ＮＰ－ｃｏｍｐｌｅｔｅ；Ｄｙｎａｍｉｃ　Ｐｒｏｇｒａｍｍｉｎｇ　

第２９卷第１期　Ｖｏｌ　２９，Ｎｏ１　温州大学学报・自然科学版　Ｊｏｕｒｎａｌ　ｏｆ　Ｗｅｎｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ・Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅｓ　２００８年２月　Ｆｅｂ．２０ｏ８　

有序组合树法求解Ｏ一１背包问题初探　

安晨，付永军　

（兰州交通大学交通运输学院，甘肃兰州　７３００７０）　

摘要：以０－１背包问题为研究对象，建立教学模型，采用有序组合树法对中小规模的背包问题进行　

求解．与传统的贪婪算法相比，该算法更容易找到最优解．并通过实例说明该算法对解决中小规模的　０－１背包问题是行之有效的．　关键词：背包问题；有序组合树；算法　

中图分类号：Ｏ２２１，４　文献标识码：Ａ　文章编号：１００６．０３７５（２００８）０１．００１０．０５　

背包问题是整数规划中一类较为特殊的问题，是一个经典的ＮＰ一完全问题，也是一个典型的　

优化难题，其计算的复杂性为Ｄ（２“）ｎ１．背包问题在现实生活中具有广泛的应用背景，如物流公　

司的货物发配问题、集装箱的装运问题以及工厂的下料问题等都可以用背包问题进行求解．解决　背包问题的算法有最优算法和启发式算法，最优算法包括穷举法、动态规划法、隐数法以及有序　组合树法　等，启发式算法包括贪婪算法、遗传算法、模拟退火算法以及禁忌搜索算法等一些智　能算法．这些算法各有优缺点，有序组合树法原理简单，操作简便．对许多算例，用有序组合树　法处理，更容易找到最优解，甚至树根即为最优解．　

１　Ｏ一１背包问题　

给定ｎ件物品和一背包，物品　的价值为ｃ』，体积为　，背包的容积为　，如何选择装入背　

包的物品，才能使得装入背包中物品的总价值最大．引入　为一０－１变量，各变量的约束如下：　

ｆ１，第ｉ件物品装入背包　．，　１　ｏ，第ｉ件物品不装入背包　，ｚ，…，　

ｌ＿　背包容量约束：　ｘｉＶｉ　Ｖ　ｉ＝１　０一Ｉ背包问题的数学模型如下：　

ｍａＸ　Ｚ＝∑　ｃｆ　

＝０或Ｉ，ｉ＝Ｉ，２，…，ｎｘ／　戤，　，，…，　趴ｔ∑　ｉ＝Ｉ　

动态规划——01背包问题

⼀、最基础的动态规划之⼀

01背包问题是动态规划中最基础的问题之⼀，它的解法完美地体现了动态规划的思想和性质。

01背包问题最常见的问题形式是：给定n件物品的体积和价值，将他们尽可能地放⼊⼀个体积固定的背包，最⼤的价值可以是多少。我们可以⽤费⽤c和价值v来描述⼀件物品，再设允许的最⼤花费为w。只要n稍⼤，我们就不可能通过搜索来遍查所有组合的可能。运⽤动态规划的思想，我们把原来的问题拆分为⼦问题，⼦问题再进⼀步拆分直⾄不可再分（初始值），随后从初始值开始，尽可能地求取每⼀个⼦问题的最优解，最终就能求得原问题的解。由于不同的问题可能有相同的⼦问题，⼦问题存在⼤量重叠，我们需要额外的空间来存储已经求得的⼦问题的最优解。这样，可以⼤幅度地降低时间复杂度。

有了这样的思想，我们来看01背包问题可以怎样拆分成⼦问题：

要求解的问题是：在n件物品中最⼤花费为w能得到的最⼤价值。显然，对于0 <= i <= n,0 <= j <= w，在前i件物品中最⼤花费为j能得到的最⼤价值。

可以使⽤数组dp[n + 1][w + 1]来存储所有的⼦问题，dp[i][j]就代表从前i件物品中选出总花费不超过j时的最⼤价值。

可知dp[0][j]值⼀定为零。那么，该怎么递推求取所有⼦问题的解呢。显⽽易见，要考虑在前i件物品中拿取，⾸先要考虑前i - 1件物品中拿取的最优情况。

当我们从第i - 1件物品递推到第i件时，我们就要考虑这件物品是拿，还是不拿，怎样收益最⼤。

①：⾸先，如果j < c[i]，那第i件物品是⽆论如何拿不了的，dp[i][j] = dp[i - 1][j];

②：如果可以拿，那就要考虑拿了之后收益是否更⼤。拿这件物品需要花费c[i]，除去这c[i]的⼦问题应该是dp[i - 1][j - c[i]]，这时，就要⽐较dp[i - 1][j]和dp[i - 1][j - c[i]] + v[i]，得出最优⽅案。