背包问题的变形二：限制背包（Bounded Knapsack）

导语

有了之前两篇关于背包问题文章的积累，《一文搞懂经典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废了，算不出结果

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