动态规划——背包问题

发表于 | 分类于

前言

近期一直在复习JavaEE方面的内容，好久没碰算法感觉脑子都快生锈了(我做的LeetCode题解已经12天没有commit了)。正好之前一直想总结一下关于动态规划的思路与理解，现在就趁着这个时间好好复习一下动态规划。当然不能纸上谈兵，我们就来解决动态规划中的一类经典问题——背包问题

背包问题

什么是背包问题？

简单来说背包问题要解决这样一类问题：有N件物品和一个容量为V的背包，并且N件物品中的第i件物品的费用是c[i]，价值是w[i]，那么将哪些物品装入背包可使物品价值总和最大并且物品重量不超过背包的容量。

0-1背包问题

分析：0-1背包问题的关键是每种物品仅有一件，可以选择放进背包或者不放进背包。按照这个思路，我们来定义动态规划的状态定义。
状态定义：f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

问题的解释：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
伪代码(用一维数组代替与上述状态定义中的二维数组，两者只是形式不同而已，后面会解释为什么这么做)：

1
2
3
for i=1..N
    for v=V..0   //使用降序循环，就可以用一维数组来描述状态，为了后续变种问题提供了方便
        f[v]=max{f[v],f[v-c[i]]+w[i]};

解析： f[v]=max{f[v],f[v-c[i]]} 就相当于我们的转移方程 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]} ， 因为当前的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。但是如果将v的循环顺序从上面的逆序改成顺序的话，那么 f[v]=max{f[v],f[v-c[i]]} 就成了 f[i][v]=max{f[i-1][v],f[i][v-c[i]]} ，显然与本题意不符。这里一定要理解才能往下看，后续的背包问题的变种问题就是基于一维数组来解决的，这里就解释了使用一维数组的原理与可行性。

状态转移方程定下来之后，完成动态规划还有一个任务就是要确定状态的初始值，也就是状态的初始化过程。关于状态的初始化是根据题目的要求来变的，有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。这两种问法的实现方法是在初始化的时候是不同的。
如果要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
如何理解要求背包恰好装满情况下的初始化呢？“字面”来理解，如果要求恰好装满背包，那么只有在f[0]的时候，背包容量为0，这时可以认为背包是满的，最大价值有解且解为0，而其它f[1..V]在初始化的时候，背包是有容量的且背包未被装满，所以初始值为-∞，可以理解为此时无解。

另外，如果要求输出这个最优值的方案的话，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下每个状态是由哪一个状态推出来的，于是就可以从最终状态找到上一个状态，再从上一个状态接着向前推即可。
以0-1背包为例，方程为 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 再用一个数组g[i][v]记录状态转移路线，如果g[i][v]==0表示f[i][v]的值是采用了方程的前一项（也即f[i][v]=f[i-1][v]），如果g[i][v]==1表示采用了方程的后一项（也即f[i][v]=f[i][v-c[i]]）。
输出方案的伪代码可以这样写：（设最终状态为f[N][V]）

1
2
3
4
5
6
7
8
9
i=N
v=V
while(i>0){
    if(g[i][v]==0)
        print "未选第i项物品"
    else if(g[i][v]==1)
        print "选了第i项物品"
        v=v-c[i]
}

ps：本篇博客重点在于梳理关于动态规划解决背包问题的思路，有得只提供了伪代码，有兴趣的同学可以自己实现一下，很简单。

背包问题变种

我们基于上述0-1背包问题来修改题目限制条件，看看有哪些变种的问题。

变种1:装满背包或者装至某一指定体积的方案总数

分析：要求得装满背包或者装至某一体积的方案总数，我们简单修改一下状态定义即可，就基于0-1背包问题来举例：
状态定义：f[i][v]表示前i件物品装满体积为v的背包的方案总数
状态转移： f[i][v]=sum(f[i-1][v],f[i-1][v-c[i]]); 前i件物品装满体积为v的背包方案数，分为2种，一种不包含第i件物品f[i-1][v]，还一种包含第i件物品f[i-i][v-c[i]]，相加即可。
初始化：f[0][0]=1;理解为将0件物品放入体积为0的背包的方案数为1。按照这种初始化与状态转移方程求解的话，f[N][V]就是用N件物品装满体积为V背包的方案数.

我自己写了了一个基于0-1背包的问题的该变种问题的求解，用的是一维数组的形式，当然也可以按照状态转移方程写出二维数组的解法。

1
2
3
4
5
6
7
8
9
10
private int dp(int[] f, int v) {
    int[] dp = new int[v + 1];
    dp[0] = 1;//将第0件物品装入体积为0的背包,只有一种方案,放入nothing
    for (int i = 0; i < f.length; i++) {
        for (int j = v; j - f[i] >= 0; j--) {//每次放入之前检查背包容量是否足够
            dp[j] = dp[j] + dp[j - f[i]];
        }
    }
    return dp[v];
}

变种2:完全背包问题

0-1背包问题一个关键点在于每种物品仅有一件，可以选择放进背包或者不放进背包。如果我们修改这个限制条件，那么问题变成这样：有N种物品(每种物品可以选任意件)和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

分析：这个问题非常类似于0-1背包问题，所不同的是每种物品有无限件，那么也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有V/c[i]+1种策略：取0件、取1件、取2件……等(最多V/c[i]件)。基于此，就可以将完全背包问题转化为0-1背包问题：考虑到第i种物品最多选V/c[i]件，于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个扩展物品数量之后的0-1背包问题。于是我们仍然可以按照0-1背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，同样写出状态转移方程：

1
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

方程的意义：将第i种物品拆分成V/c[i]件同样的物品，每件物品符合0-1背包的条件(取或者不取)，按照0-1背包的思路求解即可。
但是！上述解法虽然可行，但是比原来0-1背包问题多了一层循环，所以有人就提出了下面解法：
伪代码：

1
2
3
for i=1..N
    for v=0..V //与0-1背包不同只在于v的循环顺序，同样可以得到正确解
        f[v]=max{f[v],f[v-cost]+weight}

这个伪代码与0-1背包问题的伪代码只有v的循环顺序不同而已，比上述转化为0-1背包的解法精练很多，至于这种解法的正确性，我也没怎么想明白。希望大家可以和我一起讨论这个问题，在博客的about me界面有我的联系方式，一起进步。

变种3:分组背包问题

分组的背包问题：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

分析：这个问题变成了每组物品有若干种策略，是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有状态转移方程：

1
f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}

使用一维数组的伪代码如下：

1
2
3
4
for 所有的组k
    for v=V..0
        for 所有的i属于组k
            f[v]=max{f[v],f[v-c[i]]+w[i]}

总结

以上就是关于背包问题的解法，重点在于理解0-1背包问题的一维数组解法，由此可以解决背包问题的其他变种问题。在之前的股票中的动态规划博客中已经介绍一些关于动态规划的理解，这里在另外一个角度理解动态规划(以下是我整理的知乎高票答案得到的，感谢知乎大牛的分享)：

所有的决策类求最优解的问题都是在状态空间内找一个可以到达的最佳状态，搜索的方式是去遍历每一个点，而动态规划则是把状态空间变形，由此变成从初始到目标状态的最短路径问题。
依照上述的描述：假若你的问题的结论包含若干决策，则可以认为从初始状态到最终解的中间的决策流程是一个决策状态空间中的转移路线。但是前提是，你的状态描述可以完整且唯一地覆盖所有有效的状态空间中的所有点，且转移路线包含所有可能的路径。
这个描述是包含动态规划两大条件的。所谓无后效性，指状态间的转移与如何到达某状态无关。如果有关，意味着你的状态描述不能完整而唯一地包括每一个状态。如果你发现一个状态转移有后效性，很简单，把会引起后效性的参数作为状态描述的一部分放进去将其区分开来就可以了；最优子结构说明转移路线包含了所有可能的路径，如果不具备最优子结构，意味着有部分情况没有在转移中充分体现，增加转移的描述就可以了。最终所有的搜索问题都可以描述成状态空间内的状态转移方程，只是有可能状态数量是指数阶的，有可能不满足计算要求罢了。
于是从状态图的角度抽象，所有的动态规划问题都可以转变为状态空间内大量可行状态点和有效转移构成的图的从初始状态到最终状态的最短路问题，其本质就是图论中的最短路径问题。

0%