背包问题的变形一：无限制背包（Unbounded Knapsack）

导语

之前写过一篇《一文搞懂经典0-1背包问题》，n个物品放入包中，每件只能选择放一次，放过之后就不能再放了。当时分析了三种算法，一个是递归搜索（在n<20，W特别大时适用），一种是记忆化递归，最后是动态规划算法，记忆化递归和动态规划都依赖于子问题有重复，否则，最糟糕的情况下，每件物品都是不同的2的幂次方重量，就会退化到递归搜索。今天要再深入讨论两个变形题目，一个是无限制的背包问题，一个是有限制的背包问题，今天先讨论下无限制的背包问题。

无限制背包（Unbounded Knapsack Problem）

简单说每件物品没有数量限制，随便放入包中。关于这个算法，有三种解法。基本思路都是虚拟出所有的物品，因为有总重量限制，每件物品放入背包中的数量总是有上限的。
先看下0-1背包问题动态规划实现方法的源码：

func knapsack01D(w []int, v []int, W int) int {
    n := len(w)
    dp := make([]int, W+1)
    for i := 0; i < n; i++ {
        for j := W; j >= w[i]; j-- {
            dp[j] = max(dp[j-w[i]]+v[i], dp[j])
        }
    }

    r := 0
    for i := 0; i <= W; i++ {
        if dp[i] > r {
            r = dp[i]
        }
    }

    return r
}

这里把更新dp数组的部分，包装成一个函数knapsack01，如下：

func knapsack01(dp []int, w int, v int) {
    W := len(dp)
    for j := W-1; j >= w; j-- {
        dp[j] = max(dp[j-w]+v, dp[j])
    }
}

第一种方法，是把每件东西可以选择数量都虚拟出来（naive），比如第i件重量w[i]，那么第i件东西最多有W/w[i]件，然后就变成每件虚拟的物品扔给knapsack01更新dp数组的部分。

func knapsackUnbounded1(w []int, v []int, W int) int {
    n := len(w)
    dp := make([]int, W+1)
    for i := 0; i < n; i++ {
        m := W/w[i]
        for j := 0; j < m; j++ {
            knapsack01(dp, w[i], v[i])
        }
    }

    r := 0
    for i := 0; i <= W; i++ {
        if dp[i] > r {
            r = dp[i]
        }
    }

    return r
}

算法时间复杂度为O(NW^2)，空间复杂度O(W)（已经通过滚动数组优化）。

第二种方法，控制虚拟出的物品数量更少（smart），以不同的2的幂次方虚拟出物品，对于第i件物品，最多能放W/w[i]件，第i件物品的虚拟物品为，w[i]2^0、w[i]2^1、w[i]2^2……w[i]2^logW/w[i]，代码如下：

func knapsackUnbounded2(w []int, v []int, W int) int {
    n := len(w)
    dp := make([]int, W+1)
    for i := 0; i < n; i++ {
        m := math.Ilogb(float64(W)/float64(w[i]))
        for k := 0; k <= m; k++ {
            knapsack01(dp, w[i] << k, v[i] << k)
        }
    }

    r := 0
    for i := 0; i <= W; i++ {
        if dp[i] > r {
            r = dp[i]
        }
    }

    return r
}

算法时间复杂度为O(NWlogW)，空间复杂度O(W)（已经通过滚动数组优化）。

第三种方法，实现上是最简单的，但也是最难想到的，原先我们做dp更新时，故意将j的迭代顺序从W最大值逆向迭代到当前物品重量w，其实我们只需要改为顺向迭代即可，更新dp函数knapsack01改为knapsackComplete，代码如下：

func knapsackComplete(dp []int, w int, v int) {
    W := len(dp)
    for j := w; j < W; j++ {
        dp[j] = max(dp[j-w]+v, dp[j])
    }
}

整体的背包问题代码变为：

func knapsackUnbounded3(w []int, v []int, W int) int {
    n := len(w)
    dp := make([]int, W+1)
    for i := 0; i < n; i++ {
        knapsackComplete(dp, w[i], v[i])
    }

    r := 0
    for i := 0; i <= W; i++ {
        if dp[i] > r {
            r = dp[i]
        }
    }

    return r
}

算法时间复杂度为O(NW)，空间复杂度O(W)（已经通过滚动数组优化）。

可以这么优化的原因，我通过下面这个简单例子说明：

红色的箭头就是表示，我同一件物品可以反复取，直到即将超过W最大重量为止，比如在i=2时，计算dp[5]，从dp[3]变化过来的，dp[3]此时已经使用过w[2]了，但没关系。因为此时第2件物品可以反复使用。（自己去想想，理解这个点，是无限制背包问题里面最难的）。

性能测试

上面进行了理论时间复杂度的分析，我跑了下性能，设置W=10000，w物品数量1001，w取值[11,22]，v取值[7,33]，测试下来的性能符合理论分析，knapsackUnbounded3 优于 knapsackUnbounded2 优于 knapsackUnbounded1，并且knapsackUnbounded1基本上无法work了，在W=10000、w取值[11,22]时，耗时大概已经达到11s。

knapsackUnbounded3=29088, time_cost=9.429946ms
knapsackUnbounded2=29088, time_cost=151.371282ms
knapsackUnbounded1=29088, time_cost=11.718217767s

下面有时间再分析下有限制的背包问题，这个问题是背包变形问题中较为复杂的。