前言

前文用较多篇幅介绍了动态规划算法的套路，以后的文章可能就不用这么多篇幅描述详细的思考过程。

现在再来解决一个更加实际的问题，背包问题。

背包问题

给你一个背包，它的最大可承载的重量是W kg。 另外，再给你N个物品，每个物品有它自己的重量(kg)和价值($)。

求：得出该背包可以装载的最大价值的物品组合。

显然，这是一个求最值的问题，它求的是在所有允许的物品组合之下的最大价值是多少？

基于这个题目，我设定：

• 背包容量W = 18 kg

N 个物品，用容量为N的数组来表示：

• N个物品的各自重量 = [1,4,9,7,2] kg

• N个物品的各自价值 = $ [3,6,8,1,5]

先用肉眼来看一下这个问题的思考方式：

一共只能装18kg，那么，我现在，

选择装入重量为 1+9+7 = 18 kg的三件物品，

其对应的价值总数为：3+8+1 = $12。

这便是其中一种物品组合，选择重量为 1,9,7 的物品，总价值为$12.

如果我们可以求出所有的这种组合方式，那就可以直接得出最大价值的物品组合。

状态转移方程

要列出状态转移方程，首先要明确状态是什么?

这个问题中的状态是，只允许对前几件物品进行选择，以及 背包允许的总重量 ，要求的最优解是 最大物品价值

这里状态有两个，之前凑零钱问题的状态只有一个,那就是 零钱总额, 现在这里有两个状态，情况复杂了一倍。我选择使用二维数组来表示 本问题的最优解。

f(a,w) = v( 0 < a <= n )

• a 表示，只允许对前i件物品进行选择。
• n 表示 物品的总件数。
• w 表示，背包允许的总重量。
• v 这种情况下的最大物品价值。

根据这个定义，我们要求的最终答案就是: f(n,w)

根据这个定义写出伪代码：

val f[n][w]
val wt = [1,4,9,7,2]// 所有物品的各自重量
val vt = [3,6,8,1,5]// 所有物品的各自价值
f[0][]=0 // 物品数目为0，最有价值自然就是0，因为没有物品
f[][0]=0 // 背包最大重量为0，装不下任何物品，最大价值也是0

// 双重遍历，列举所有可能情况，所有物品的都要面临放进去，和不放进去的选择
for(a in 1..n){// 遍历所有物品
    for(x in 1..w){// 遍历所有重量 
        f[a][x]=max(//择优求较大值
            不把物品a装进背包，
            把物品a装进背包
        )
    }
}

解读上面的伪代码：

物品一共n件，重量一共w，外层循环 从1一直遍历到n，内层循环，x从1遍历到w，最大价值进行max择优求较大值

接下来的问题就是，如何将 不把物品a装进背包 以及 把物品a装进背包, 转化成伪代码。

思考，

如果没有把 物品a装进背包，那么，按照 f(a,w)的定义，最大价值应该等于 f(a-1,x), 因为少了一个第a件物品。

如果再把物品a装进背包，那么，此时的最大价值应该等于，去掉这件物品时的最大价值，加上，这件物品的价值, 也就是：f(a-1,x-wt[a])+vt[a]

再整合一下伪代码，就变成了：

val f[n][w]
val wt = [1,4,9,7,2]// 所有物品的各自重量
val vt = [3,6,8,1,5]// 所有物品的各自价值
f[0][]=0 // 物品数目为0，最优价值自然就是0，因为没有物品
f[][0]=0 // 背包最大重量为0，装不下任何物品，最大价值也是0

// 双重遍历，列举所有可能情况，所有物品的都要面临放进去，和不放进去的选择
for(a in 1..n){// 遍历所有物品
    for(x in 1..w){// 遍历所有重量 
        f(a,x)= max(//择优求较大值
            f(a-1,x)，
            f(a-1,x-wt[a])+vt[a]
        )
    }
}

如果到了这里还有点晕，举个实例：

• 按照上面的伪代码，当a=1(只允许选第一件物品)，且x=1时，

  f(1,1) = max(
    f(0,1),
      f(0,1-wt[1])+vt[1]
  )
  

  得到

  f(1,1) = max(0,3) = 3
  

• 而当a=2（允许选择前两件物品是否放入背包），x=1

  f(1,1)=3
  f(2,1)=max(
    f(1,1),
      f(1,1-1)+vt(2)
  ) = max(3,6) = 6
  

当a=2，其实前面已经计算出了f(1,1)可以直接使用。

以此类推，内外双重循环足以列举出所有物品，在所有最大重量下的最优总价值。

思路已经明确了，那么可以开始写状态转移方程了吧。

但是臣妾做不到 = =！不是我不想，是我不知道怎么用数学公式来表示双重循环，临时去研究word数学公式又觉得划不来，所以算了吧。上面的伪代码已经可以代表完整的解题思路了，接下来只需要把伪代码换成真正的可执行kotlin代码就行了。

开始撸码

var wt = intArrayOf(1, 4, 9) // 物品各自重量
var vt = intArrayOf(3, 6, 8) // 物品各自价值

var totalWeigh = 10 // 要求的总重量
var res = Array(wt.size + 1) { IntArray(totalWeigh + 1) } // 结果二维数组

/**
 * 因为当最大重量是0时，或者当物品前N件物品，N=0时，都没有意义。所以此时的最优价值都是0
 */
fun initRes() {
    for (i in wt.indices) {
        for (j in 0 until totalWeigh) {
            if (i == 0 || j == 0) {
                res[i][j] = 0
            }
        }
    }
}

fun cal(): Int {
    initRes()
    for (a in 1..wt.size) {
        for (x in 1..totalWeigh) {
            val before = res[a - 1][x] // 不放进去的值
            if (x - wt[a - 1] < 0) { // 背包容量比物品重量还要小，那就不能放进去
                res[a][x] = before
            } else {
                val now1 = res[a - 1][x - wt[a - 1]]
                val now2 = vt[a - 1]
                res[a][x] = max(before, now1 + now2)
            }
        }
    }
    return res[wt.size][totalWeigh]
}


fun main() {
    val res = cal()
    println(res)
}

运行结果:

11

此结果表示：

在物品各自重量(1, 4, 9)kg，各自价值11

问题解决。

时间/空间复杂度

• 子问题的个数

  假设物品数组的size是N，背包总重量是：W*N，因为存在双重遍历

• 解决一个子问题花费的时间

  只有一次max运算，所以花费时间1

• 解决一个子问题花费的空间

  每一个子问题都要记录一次 res [a] [x]····所以空间1

时间复杂度 O(WN) , 空间复杂度 O(WN)

问题变形

上面的背包问题的算法，说到底还是数学思维转变成程序代码，其本质还是数学。然而数学思维，解决的并不是一个问题，而是一类问题。比如下面的问题：

子集分割问题：

给定一个正整数的数组 , 问，能否把这个数组分隔成两个子集，使得两个子集中元素之和相等。

例如：

数组为：[1,5,11,5]，输出：可以分割为两个子集[11],[1,5,5]

数组为：[1,2,3,5], 输出，无法分隔为两个元素之和相等的子集.

这个问题看似与本文的背包问题毫无关联，但是，如果换一种形式来说明：

给定一个承重为 sum/2 的背包，以及n件物品，每一件物品都有它的重量，是否存在一种方法，用这些物品刚好填满背包。

这恰好就是一个标准的背包问题，比上一节的背包问题还简单一些.

状态转移方程

明确状态：

一共有n件物品可以选择，第一个状态就是 前N件物品可供选择。第二个状态是，背包的承重W。每一个物品都面临两种选择，装进背包和不装进背包.

背包问题的套路, 每一个状态都由一个数组维度表示，多重循环所有状态，然后对结果择优：

本题的结果值表示成： f [i] [j] = x

f 表示函数，i 表示前i件物品可供选择，j 表示背包可承重。x 表示是否有刚好填满背包的方法，值 true/false

如，f [4] [11] = true ，则表示，用前4件物品，背包承重为11，存在刚好填满背包的方法。

我们最终要求的答案就是：f [N] [sum/2] = ？

明确了状态，那么状态是如何转移的？

f [i] [j] = x 表示的是前i个物品可以选择，总承重为j，是否存在刚好填满的方法。

状态是存在依赖性的，后一个状态，会依赖于前一个状态。

思考

那么如果不把第i个物品装入背包,背包承重仍然是 j，是否仍然存在刚好填满的方法？ 这取决于 f [i-1] [j]

如果我把第i个物品装入背包，是否存在刚好填满的方法, 写成数学式子：f [i-1] [ j - wt[i] ] （wt是一个数组，wt[i] 表示第i个物品的重量）

举个实例

假设物品的重量是 [1, 3, 4, 6, 6], 那么 sum/2 = (1+3+4+6+6) = 10 ,背包承重是10.

基准状态：f [1] [0] = true 表示，使用前1个物品，背包承重为0，一定有办法可以装的下,那就是，不放入任何物品。

要求：f [1] [1] ，由于第一个物品的重量是1，背包承重也是1，所以，放的下去，

f [i-1] [ j - wt[i] ] 替换成实际值：f [1] [1] = f[1-1] [1-1] = f [0] [0] = true, 表示，使用前1个物品，存在刚好装满背包的方法。

求 : f [1] [2] , 第一个物品的重量是1，背包总重是 2,所以放得下，f [1] [2] = f [1-1] [2-1] = f [0] [1] = false ，不存在刚好装满背包的方法。这也是基准情况的一种，没有任何物品，背包容量大于0，肯定是装不满背包的，所以结果是 false.

f [2] [1] 第二件物品的重量是3，背包总承重是 1，所以放不下第二件物品，所以f [2] [1] = f [1] [1] = true. 也就是说，第二件物品相当于没有参与计算。

f [2] [3] 背包总承重是3，放得下第二件物品，所以 f [2] [3] = f [1] [3-3] = f [1] [0] = true , 所以，存在刚好装满的方法。

撸码

把上面的思路，写成kotlin程序代码,考虑一些特殊情况，比如数组总数是奇数,背包总承重是0 等：

fun canPartition(arr: IntArray): Boolean {
    var sum = 0
    for (num in arr) sum += num
    if (sum % 2 != 0) return false// 和为奇数时，不可能划分成两个和相等的集合
    val n = arr.size
    sum /= 2
    val dp = Array(n + 1) { BooleanArray(sum + 1) }
    // 初始化，除了总重量为0的情况之外，所有的值都变成false
    for (i in dp.indices) {
        for (j in dp[i].indices) {
            dp[i][j] = j == 0
        }
    }

    //开始遍历
    for (i in 1..n) {
        for (j in 1..sum) {
            if (j - arr[i - 1] < 0) { // 背包容量不足，不能装入第 i 个物品
                dp[i][j] = dp[i - 1][j] // 直接忽略第i个物品
                //println("装不下，继承之前的结果：dp[$i][$j] = ${dp[i][j]}")
            } else {// 装的下
                val notPut = dp[i - 1][j] // 如果不装下去，是否存在刚好填满的情况
                val put = dp[i - 1][j - arr[i - 1]] // 如果装下去，是否存在刚好填满的情况
                dp[i][j] = notPut or put // 这两种情况，只要有一种满足刚好填满，就是能够刚好填满
                //println("装得下，继承之前的结果：dp[$i][$j] = ${dp[i][j]}")
            }
        }
    }
    return dp[n][sum]
}

fun main() {
    val s: Boolean = canPartition(intArrayOf(1, 3, 4, 6, 6))
    println("s:$s")
}

执行结果：

s:true

在 正整数数组 1, 3, 4, 6, 6 中，存在平均分割子集的情况。心算一下，[1,3,6] [4,6] . 问题解决。

时间/空间复杂度

• 子问题的个数

  假设物品数组的size是N，背包总重量是：sum/2，因为存在双重遍历

• 解决一个子问题花费的时间

  只有一次or运算，所以花费时间1

• 解决一个子问题花费的空间

  每一个子问题都要记录一次 dp[i][j]····所以空间1

时间复杂度 O(sumN/2) , 空间复杂度 O(sumN/2)

总结

经过这几篇动态规划案例的解析，对于动态规划算法的完整套路基本上可以归纳如下：

1. 明确状态和选择，

   像背包问题，状态就是 前N件物品可供选择这里的N，以及 当前背包的承重W，像凑零钱问题，状态就是 当前目标金额， 所谓状态，就是可以推移演变的量，如果最终要求的是 f [N] [W] , 那就让状态推移，有几个状态，就几重遍历，外层遍历从 1 到 N ,内层遍历 从 1 到 W 。

   选择：背包问题的选择， 就是这个物品，放进去，或者 不放进去，这是一个选择。凑零钱问题，该零钱放进去或者不放进去，是一个选择。

2. 定义结果数组：

   背包问题由于有两个状态在推移，所以，用了二维数组来表示结果 f [N] [W] ,凑零钱问题则只需要 一维数组 f[n] 即可.

3. 根据 选择，得出状态转移的逻辑

   当前结果： f [N] [W] 是经过状态转移，一步一步，从初始状态 （Base case）f [0] [...] 和 f [..] [0] 慢慢往后推移的出来的。而，背包问题中，在选择 要不要把 当前物品放进去，放进去是一种计算方式，不放进去，是另一种计算方式。按照我们的目标，对不同选择造成的结果 进行择优，保存到结果数组中，就得出了后续的结果的依赖。

   本来我很想写成数学公式的，但是介于数学修养实在有限，只能写伪代码来表现逻辑。

4. 上面的过程都确认无误的话，最后一步才是编写程序代码。

算法的学习，水很深，路漫漫，共勉！