动态规划-01背包

2020-07-21 本文已影响0人 vicentwyh

问题描述

有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：物品数量＝4，背包容量(V)＝8 ，物品的体积(W)和价值(V)如下：

背包问题的解决过程：

首先定义为一些变量，方便描述方便：
Xi：第i个物品的选择（xi = 1 代表选择该物品，0则代表不选）
Vi：代表第i个物品的价值，
Wi：代表第i个物品的体积

建立模型：问题的解为求 Max(X1V1 + X2V2 + ......+XnVn)
约束条件：X1W1 + X2W2 + ......+XnWn <= V
确定递推关系式：
定义f(i,j)，表示前 i 个物品装入容量为 j 的背包的最大价值。
此时对于第 i 个物品，有两种可能：

背包剩余容量不足以容纳该物品，此时背包的价值与前i-1个物品的价值是一样的，f(i,j) = f(i-1,j)
背包剩余容量可以装下该商品，此时需要进行判断，因为装了该商品不一定能使最终组合达到最大价值，如果不装该商品，则价值为：f(i-1,j)，如果装了该商品，则价值为f(i-1,j-wi) + vi，从两者中选择较大的那个。
所以就得出了递推关系式：

j < Wi: f(i,j) = f(i-1,j)
j >= Wi: f(i,j) = Max( f(i-1,j)，f(i-1,j-wi) + vi )

确定初始值：
01背包问题一般有两种不同的问法：
（1）一种是恰好装满背包的最优解，要求背包必须装满，那么在初始化的时候，除了f(0)(0)为0，其他的f(j)(1 <= j <= 背包容量)都应该设置为−∞，这样就可以保证最终得到的f(i)(j)是恰好装满背包的最优解。
（2）另一种问法不要求装满，而是只希望最终得到的价值尽可能大，那么初始化的时候，应该将f(j)(0 <= j <= 背包容量)全部设置为0。

为什么呢？
因为初始化的数组，实际上是在没有任何物品可以放入背包的情况下的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么都不装且价值为0的情况下被“恰好装满”，其他容量的背包均没有合法的解，因此属于未定义的状态，应该设置为−∞。如果背包不需要被装满，那么任何容量的背包都有合法解，那就是“什么都不装”。这个解的价值为0，所以初始状态的值都是0。

递归解法：

class Solution {
    
    // 体积
    let volumn:[Int] = [0,2,3,4,5]
    // 价格
    let price:[Int] = [0,3,4,5,6]

    func findMaxPrice(_ capital: Int) -> Int {
        let maxPrice = dfs(volumn.count - 1, left: capital)
        return maxPrice
    }
    
    func dfs(_ i: Int,left capital: Int) -> Int {
        var result = 0
        if capital == 0 || i == 0 {
            result = 0
        } else if capital < volumn[i] {
            result = dfs(i - 1, left: capital)
        } else {
            let tmp1 = dfs(i - 1, left: capital)
            let tmp2 = dfs(i - 1, left: capital - volumn[i]) + price[i]
            result = max(tmp1, tmp2)
        }
        return result
    }
}

每个物品需要递归调用两次，时间复杂度：O(2ⁿ)，n为物品数量

动态规划解法：

判断是否可以使用动态规划求解：
最优化原理:使用反证法：
假设(x1，x2，…，xn)是01背包问题的最优解，则有(x2，x3，…，xn)是其子问题的最优解，假设(y2，y3，…，yn)是上述问题的子问题最优解，则有(v2y2+v3y3+…+vnyn)+v1x1 > (v2x2+v3x3+…+vnxn)+v1x1。说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理。

无后效: 对于任意一个阶段，只要背包剩余容量和可选物品是一样的，那么我们能做出的现阶段的最优选择必定是一样的，是不受之前选择了什么物品所影响的。即满足无后效性。

class Solution {
    
    // 体积
    let volumn:[Int] = [0,2,3,4,5]
    // 价格
    let price:[Int] = [0,3,4,5,6]
    func findMaxPrice(_ capital: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: capital + 1), count: volumn.count)
        
        for i in 1..<volumn.count {
            for j in 1...capital {
                if j < volumn[i] {
                    dp[i][j] = dp[i - 1][j]
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volumn[i]] + price[i])
                }
            }
        }
        return dp[volumn.count - 1][capital]
    }
}

两次循环遍历嵌套，时间复杂度O(n*c)，n为物品的数量，c为背包容量

比较递归和动态规划解法时间复杂度：O(2ⁿ) 、 O(n*c)，可以预见，当数据量越大，相比递归算法，动态规划用于有力的优势

01背包算法优化：

上方法的时间和空间复杂度均为O(NC)，时间复杂度已经不能再优化了，但空间复杂度却可以优化到O(C).

回头看下之前的递推关系式：

j < Wi: f(i,j) = f(i-1,j)
j >= Wi: f(i,j) = Max( f(i-1,j)，f(i-1,j-wi) + vi )

可以发现，每次求解 f(i,j)只与f(i-1,m) {m:1...j}有关。也就是说，如果我们知道f(i-1,1...j)就肯定能求出f(i,j)，为了更直观的理解，请看下面表格：

class Solution {
    
    // 体积
    let volumn:[Int] = [0,2,3,4,5]
    // 价格
    let price:[Int] = [0,3,4,5,6]
    
    func findMaxPrice(_ capital: Int) -> Int {
        var dp = Array(repeating: 0, count: capital + 1)
        
        for i in 1..<volumn.count {
            //注意：j需要按照 背包最大容量...0的逆序来循环
            for j in (volumn[i]...capital).reversed() {
                dp[j] = max(dp[j], dp[j - volumn[i]] + price[i])
            }
        }
        return dp[capital]
    }
}

注意：使用一维数组时，j 应按照 背包容量 -> w[i]的顺序进行遍历，即逆序遍历。这是为了保证第 i 次循环中的状态f[i][j]是由组状态f[i−1][j−w[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果f[i−1][j−w[i]]。

那为什么会这这样呢？

相比二维数组的背包把各个状态都保存了下来，一维数组的背包是会覆盖之前的状态的，即 f[j] 的第 i 次遍历结果会覆盖第 i - 1 的结果：
f[j]表示在执行i次循环后(此时已经处理iii个物品)，前 i 个物体放到容量 j 的背包时的最大价值，即之前的 f[i][j]。与二维相比较，它把第一维压去了，但是二者表达的含义是相同的，只不过 f[j] 一直在重复使用，所以，也会出现第i次循环覆盖第i−1次循环的结果。

这个说可能有点抽象，用表格解释下