动态规划-02完全背包

问题描述

有n个物品，它们有各自的体积和价值，现有给定容量V的背包，每种物品都就可以选择任意数量，如何让背包里装入的物品具有最大的价值总和？

这个问题类似于动态规划-01背包，所不同的在于每种物品无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。

仍然按照解01背包时的思路，令f[i][j]表示前i种物品恰放入一个容量为V的背包的最大价值。
用f(i,j)表示前i种物品放入一个容量为j的背包获得的最大价值，那么对于第i种物品，我们有k种选择，0 <= k * V[i] <= t，即可以选择0、1、2...k个第 i 种物品，所以递推表达式为：

仍然可以按照每种物品不同的策略找出递推关系，写出状态转移方程：

0 <= k * v[i] <= V： f(i,j) = Max{ f(i-1,j)，f(i-1,j-vi *k) + vi * k }

递归解法：

简单暴力循环，嵌套一个关于k的循环，第 i 种物品可选数量 k ∈ [0,V/v[i]]

class Solution {
    
    // 体积
    let v:[Int] = [0,5,7]
    // 价格
    let p:[Int] = [0,5,8]
    func findMaxPrice(capital V: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: V + 1), count: v.count)
        
        for i in 1..<v.count {
            for j in v[i]...capital {
                var k = 0
                while k * v[i] <= j {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i] * k] + p[i] * k)
                    k += 1
                }
            }
        }
        return dp[v.count - 1][V]
    }
}

求解 f[i][j] 的时间是 O(V/v[i])，总的复杂度可以认为是 O(N∗Σ(V/v[i]))，是比较大的。

转化为01背包问题再求解。既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解

最简单的想法：考虑到第 i 种物品最多选 V/v[i] 件，于是可以把第 i 种物品转化为 V/v[i] 件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
更高效的转化方法是：二进制的思想，把第 i 种物品拆成费用为 v[i]∗2^k，价值为 v[i]∗2^k 的若干件物品，其中 k 满足v[i]∗2k<=V。因为不管最优策略选几件第 i 种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/v[i]))件物品，是一个很大的改进。

时间：O(VN)，空间：O(V)的最优算法。01背包中用 j 逆序遍历（即 V -> 0 ）的顺序实现了二维数组到一维数组的优化转化。
类似的完全背包也可以进行非常相似的优化：

for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= V; j++)
        f[j] = max(f[j], f[j - v[i]] + p[i]);

这个代码与01背包的代码只有 j 的循环次序不同而已。
01背包中要按照 j=V...0 的逆序遍历。这是因为要保证第 i 次循环中的状态 f[i][j] 是由状态 f[i−1][j−v[i]] 递推而来。换句话说，这正是为了保证每件物品只选一次。
而完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时，却正需要一个可能已选入第 i 种物品的子结果 f[i][j−v[i]]，所以就可以并且必须采用 j=0...V的顺序循环。这就是这个简单的程序为何成立的道理。值得一提的是，上面的伪代码中两层for 循环的次序可以颠倒，这个结论有可能会带来算法时间常数上的优化。

完整的代码如下：

class Solution {
    
    // 体积
    let v:[Int] = [0,5,7]
    // 价格
    let p:[Int] = [0,5,8]
    func findMaxPrice(capital V: Int) -> Int {
        var dp = Array(repeating: 0, count: V + 1)
        
        for i in 1..<v.count {
            for j in v[i]...V {
               dp[j] = max(dp[j], dp[j - v[i]] + p[i])
            }
        }
        return dp[V]
    }
}

这里我们不再讲解递归解法，有兴趣可以自行尝试。

最后编辑于：2020.09.18 01:16:55