导语

有了之前两篇关于背包问题文章的积累，《一文搞懂经典0-1背包问题》和《背包问题的变形一：无限制背包（Unbounded Knapsack）》，今天讨论的背包问题另一个变形问题，限制背包（Bounded Knapsack）就容易理解得多了。限制背包的意思是每样物品不是只有一件，也不是无限数量，给定一个限制数量，求取装满背包获得的最大价值。那么这个问题利用之前积累的知识很容易解决。背包问题可以由浅入深，而且层层递进，经过这次的学习，我发现迷上了这个经典的NPC问题。

限制背包（Bounded Knapsack Problem）

最容易想到的还是把每件物品按照数量限制（naive），一件件取出，然后更新之前定义的dp数组（见《一文搞懂经典0-1背包问题》），OK，源代码修改下之前无限制背包问题的，也很简单：

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

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

    return r
}

数组m给出的是物品的数量限制。算法时间复杂度O(NW*Sigma(m[i]))，空间复杂度O（W）（已经通过滚动数组优化）。

如果要进行优化，自然想到了之前smarter的方式，按2的幂次方去组合出虚拟物品来，这样考虑的物品数量大大降低了，但是恶心的是，不像无限制背包，我们每件物品都可以随便取，直到超过重量上限。这里，我们需要按两种方式考虑，如果m[i]w[i] >= W，OK，那直接使用knapsackComplete更新dp数组即可，如果m[i]w[i] < W，那么我们尝试尽可能拆分虚拟物品，比如m[i] = 19，那么可以拆出的虚拟物品组合为（1, 2, 4, 8)倍原来的物品，剩下19-(1+2+4+8)=4倍物品，我们单独考虑。代码如下，稍微复杂些，仔细看，应该不难理解：

func knapsackBounded2(w []int, v []int, m []int, W int) int {
    n := len(w)
    dp := make([]int, W+1)
    for i := 0; i < n; i++ {
        if m[i] * w[i] >= W {
            knapsackComplete(dp, w[i], v[i])
            continue
        }

        left := m[i]
        for k := 0; k < math.Ilogb(float64(m[i])); k++ {
            knapsack01(dp, w[i] * 1<<k, v[i] * 1<<k)
            left -= 1<<k
        }

        for j := 0; j < left; 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*Sigma(m[i]))，空间复杂度O（W）（已经通过滚动数组优化）。

性能测评

参数设置，W=100000，w取值[11, 220]，长度10001，v取值[7, 33]，m取值[5, 100]，测试性能如下：

knapsackUnbounded3=281800, time_cost=778.899197ms
knapsackBounded2=195626, time_cost=16.464975377s
knapsackBounded1=195626, time_cost=1m27.138384055s

看上去这个参数下，基本上算法耗时都很高了，相当于有10w件不同的商品，虚拟一下，knapsackBounded2的商品数量达到了200w左右，然后通过动态规划计算（重复子问题其实没那么高），如果可以大部分进入到m[i] * w[i] >= W，性能会比较好些，试了下面这组参数，W=100000，w取值[1000, 2000]，长度10001，v取值[7, 33]，m取值[1000, 2000]，性能结果如下：

knapsackUnbounded3=3168, time_cost=769.803021ms
knapsackBounded2=3168, time_cost=1.718676383s
knapsackBounded1废了，算不出结果

到此为止，背包问题的讨论蛮多了，我感觉自己又重新上了一遍大学的课程，温故而知新，慢慢来，学习是长跑，不追求一蹴而就，追求的是细水长流。

导语

之前写过一篇《一文搞懂经典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

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

背景

记得在大学课程中，修过《算法和数据结构》，其中的0-1背包问题，是非常经典的算法题目，当时上课时，听老师讲完后，懂了个大概，工作若干年后，已经都忘记得差不多了，印象深刻的就是往背包里面塞东西，有个重量限制，问能取得的最大价值是多少。当时最naive的想法是，贪心不就完了，用价值/重量比最高的往里面塞就可以了，但其实这个贪心解法在0-1背包问题上是不work的。对于0-1背包问题，贪心选择之所以不能得到最优解是因为：它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。（原因引用出处）最近，我想看看0-1背包问题，到底有什么算法求解，是最合适的，也是最合理的，所以开始翻阅了资料，自己动手实现了代码，也就有了此文。

问题

说了这么多，在这篇文章中，您将看到以下内容：

1. 0-1背包问题的三种实现，时间复杂度和空间复杂度分析；
2. 针对上述的代码实现，构建实际测试用例，看实际case下的benchmark数据；

讨论

0-1背包问题（NP-Complete）

问题定义，给定N个物品，w[i]表示第i件物品的重量，v[i]表示第i件物品的价值。给你一个背包，总重量限制为W。求这个背包可以装下物品的最大价值和，注意，每个物品最多用一次。
解法1. 组合搜索
使用一个长度为n的二进制string，表示x0x1……xn。其中xi要么是0要么是1，0表示该物品不放入背包，1表示放入背包。尝试所有的可能组合。时间复杂度O(2^n),空间复杂度O(n)。该实现时间复杂度较高，一般只能在n很小的时候使用，一般为n <= 20，而且v,W >> 10^6。
代码实现如下：

func knapsack01C(v []int, w []int, W int) int {
    defer time_cost(time.Now(), "knapsack01C")
    r := 0
    var help func(s int, c_w int, c_v int)
    help = func(s int, c_w int, c_v int) {
        if c_v > r {
            r = c_v
        }

        for i := s; i < len(v); i++ {
            if c_w+w[i] <= W {
                help(i+1, c_w+w[i], c_v+v[i])
            }
        }
    }

    help(0, 0, 0)

    return r
}

解法2. 记忆化递归
定义dp(i,j)为使用前i个物品，在重量为j获取到的最大价值，dp(*,0) = 0。关键是把(i,j)看作一个状态(state)，这个state下最大的价值作为值记忆化存起来，再此求解到相同状态，直接返回之前求解的值即可。
举个实例：
v = {1, 2, 4, 5}
w = {1, 1, 2, 2}

解法2的时间复杂度，O(NW)，空间复杂度，O(NW)，如果重量w = {1, 2, 4, 8……, 2^n}，那么会退化为解法1，不会有上图中重复子问题的出现，可见记忆化递归和下面要讲的动态规划，都是基于问题是否存在大量的重复子问题，如果没有，意义不大。
代码实现如下：

func knapsack01R(v []int, w []int, W int) int {
    defer time_cost(time.Now(), "knapsack01R")
    n := len(v)
    dp := make(map[[2]int]int)
    var help func(i int, l_w int) int
    help = func(i int, l_w int) int {
        if i == 0 {
            return 0
        }

        k := [2]int{i, l_w}
        t, ok := dp[k]
        if ok {
            return t
        }

        l, r := 0, 0
        if l_w >= w[i-1] {
            l = help(i-1, l_w-w[i-1]) + v[i-1]
        }
        r = help(i-1, l_w)

        ret := 0
        if l > r {
            ret = l
        } else {
            ret = r
        }

        dp[k] = ret
        return ret
    }

    r := 0
    for i := 0; i <= n; i++ {
        t := help(i, W)
        if t > r {
            r = t
        }
    }
    return r
}

解法3. 动态规划
这个方式与方法2记忆化递归方法类似。
定义dpi为使用前i个物品，在重量为j时获取到的最大价值。状态转移方程：
dpi = dpi-1 j < w[i] or max{dpi-1]+v[i], w[i] <= j <= W}
ans = max{dpN}
时间复杂度为O(NW)，空间复杂度O(NW)。空间复杂度通过滚动数组，可以降维到O(W)。什么时候使用此解法？一般n > 20并且N、W在10^6~10^7数量级。
代码实现如下：

func knapsack01D(v []int, w []int, W int) int {
    defer time_cost(time.Now(), "knapsack01D")
    n := len(v)
    var dp [][]int
    for i := 0; i <= n; i++ {
        row := make([]int, W+1)
        dp = append(dp, row)
    }

    for i := 0; i <= n; i++ {
        dp[i][0] = 0
    }

    for j := 0; j <= W; j++ {
        dp[0][j] = 0
    }

    for i := 1; i <= n; i++ {
        for j := 0; j <= W; j++ {
            dp[i][j] = dp[i-1][j]
            if j >= w[i-1] && dp[i-1][j-w[i-1]]+v[i-1] > dp[i][j] {
                dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]
            }
        }
    }

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

    return r
}

空间复杂度可以从O(NW)降低到O(W)，使用的是动态规划最常规的方案，滚动数组，注意复值的顺序，应该从数组尾端到头部赋值，代码如下：

func knapsack01D2(v []int, w []int, W int) int {
    defer time_cost(time.Now(), "knapsack01D")
    n := len(v)
    dp := make([]int, W+1)

    for j := 0; j <= W; j++ {
        dp[j] = 0
    }

    for i := 1; i <= n; i++ {
        for j := W; j >= w[i-1]; j-- {
            if dp[j-w[i-1]]+v[i-1] > dp[j] {
                dp[j] = dp[j-w[i-1]] + v[i-1]
            }
        }
    }

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

    return r
}

性能测试的benchmark
虽然上述3种解法都是可以work的，但是在性能上差别颇大，并且解法1在物品数量N<10时(W为10^5~10^6)，耗时较动态规划和记忆化递归更小，但是随着N的变大，特别是N>20开始，极速衰减性能（果然和理论值匹配），具体benchmark性能图表如下：

结束

到这里，对经典0-1背包问题的讨论暂告一个段落，可以看到0-1背包作为一个NPC问题，算法时间复杂度还是比较高的，所以一般的搜索组合算法，现在在物品数量>20时，在实际工作中是不太可行的，这个递归搜索的代码实现，唯一的优势是，代码简单易懂。但到了这里，还是不够，我后面也想在深入思考下，0-1背包问题的2个变种问题，即unbounded背包和bounded背包，这两个问题会更复杂些，但基于0-1背包问题的讨论基础上，或许会更容易理解。