Dynamic Programming 06 - Knapsack背包问题

Knapsack背包问题

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V。

0-1背包

最基础的背包问题：有N件物品和一个体积为V的背包, 每种物品均只有一件, 第i件物品的大小/重量是s[i]，价值是v[i]. 求将哪些物品装入背包可使这些物品的体积总和不超过背包体积，且价值总和最大.

对于每一个物品，只有两种结果，放入或者不放入背包，那么kn(i, j)则表示背包容量剩余j时, 前i个物品能够达到的最大值:

kn1 = kn(i-1, j-s(i)) + v(i)表示物品i放入背包后的总价值, 为前i-1物品在第i个物品占用了背包容量s(i)后的的最优解加上第i个物品的价值v(i).
kn2 = kn(i-1, j)表示物品i并没有放入背包, 等于前i-1个物品在相同背包容量的最优价值.

归纳出来的大小子问题间的关系(转移方程)为: kn(i, j) = max(kn1, kn2) = max(kn(i-1, j-s(i)) + v(i), kn(i-1, j)). 初始状态是对于不同背包剩余容量, 当没有物品可放时, 返回的最大价值一定是0. 所以背包问题, 就是二维的动态规划问题. 需要确定初始状态, 和哪些信息需要记忆.

可以简单地用一个二维数组记忆所有kn(i, j), 但要考虑到当容量非常大, 物品非常多时, 这个二维数组是很大的, 比如当(i, j) = (2000, 2000000), 会抛出java.lang.OutOfMemoryError: Java heap space. 特别是, 当每个物品的价值也比较大时, 二维数组的j维度其实利用率很低. 所以存在很多优化的空间.

优化的关键点在于减少记忆点. 注意到转移方程中:

kn(i, *)只需要用到kn(i-1, *)的值, 但我们又清楚地知道，物品在这里是没有顺序的意义的，所以这里的i仅仅是表示迭代的步骤, 只是为了遍历所有物品, 至于具体的顺序是不重要的, 所以不需要记录所有i对应的kn(i, *), 仅仅记录最近一次计算值即可. 所以我们只需要至多两个数组用来记录i-1和i对应的kn值.
kn(i, j)要用到kn(i-1, k), k<=j的值, 具体要用到哪些k是取决于i. 所以j维度的值必须都要记录下来, 以防后续需要用到.
结合起来发现只需要一个一维数组kn = new int[size + 1]即可, i对应的值可以直接在数组上更新, 不需要额外的数组记录上一次迭代的值. 在实现中, 因为kn(i, j)要用到kn(i-1, <=j)的值, 也就是kn[<j]的值不能先于kn[j]更新, 所以kn的计算要从右往左(j = size; j--).
每次决定是否加入i物品之前, 如果剩余容量j小于s[i], 那么肯定无法放入, 这个判断可以融合进j的遍历中, 因为j本身代表了剩余容量.

static int[] values;
static int[] sizes;
public static int knapsack(int size) {
    int n = values.length;
    int[] vs = new int[size + 1];
    for (int i = 0; i < n; i++) { // items
        for (int j = size; j >= sizes[i]; j--) {
            vs[j] = Math.max(vs[j - sizes[i]] + values[i], vs[j]);
        }
    }
    return vs[size];
}

优化以后空间复杂度由$\theta(NS)$降到$\theta(S)$。但时间复杂度不变.

对于0-1背包问题，如果问题变为求恰好装满时的最大值, 参考这篇博文: 此时只有容量为0的背包可能被价值为0的物品(无物品)恰好装满，初始化合法状态kn[0] = 0, kn[j > 0]为负数. 反之, 如果要求的是恰好装满时的最小值，初始化为正无穷。要注意的是改变初始化以后最后一个值是恰好装满的最大值，如果不能恰好装满，那肯定是一个负数，而且对于恰好装满的的初始化情况的不要求满的最大值是0-v背包容量的最大值。即是最后一行的MAX。

完全背包

Unbounded Knapsack: 有N种物品和一个体积为S的背包，每种物品都有无限件可用。第i件物品的体积是s[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包体积，且价值总和最大。

0-1背包的问题中每一种物品在背包中的数量只有0和1两种, 而完全背包问题每一种物品在背包中的数量是0个到k = S/s[i]个. 使用与0-1背包类似的定义, kn(i, j)表示背包容量剩余j时, 放入任意个前i个物品能够达到的最大值, 这样转移方程变为: kn(i, j) = max{kn(i-1, j-k*s(i)) + k*v(i)}, 0 <= k <= S/s[i]。可以直接在0-1背包的代码中增加一个循环，这样时间复杂度就增加了。对于取多少也可以利用二进制拆分，取的时候取1, 2, 4, ...。

完全背包的算法优化

注意到完全背包本身也包含0-1背包的情况, 0-1背包是完全背包的特例. 完全背包的kn(i, j)包含了第i种物品的数量在0 - S/s[i]所有可能选择, 并取其最大值:

若至少放一个物品i进背包, 那么在对物品i的数量进行0 - S/s[i]的遍历时, 迭代方程变为kn1 = kn(i, j-s(i)) + v(i)
若第i个物品不放入背包时, 情况和0-1背包的kn2一样, kn2 = kn(i-1, j)

所以0-1背包的迭代方程vs[j] = Math.max(vs[j - sizes[i]] + values[i], vs[j]);可以直接套用在完全背包上.

只是kn的计算要改为从左往右(j = 0; j <= size; j++). 因为此时kn1用的不再是上一次迭代的kn(i-1, j-s(i)), 而是本次迭代的kn(i, j-s(i)). 即kn(i, j)要用到kn(i, <=j)的值, 所以kn[<j]的值要先于kn[j]更新.

同样, 每次决定是否加入i物品之前, 如果剩余容量j小于s[i], 那么肯定无法放入, 这个判断可以融合进j的遍历中.

static int[] values;
static int[] sizes;
public static int unboundedKnapsack(int size) {
    int n = values.length;
    int[] vs = new int[size + 1];
    for (int i = 0; i < n; i++) { // items
        for (int j = sizes[i]; j <= size; j++) {
            vs[j] = Math.max(vs[j - sizes[i]] + values[i], vs[j]);
        }
    }
    return vs[size];
}

优化后的时间复杂度为O(NV).

在数据上也可以优化：如果物品a比b价值更高, 但体积更小, 那么完全可以不考虑物品b。对于随机生成的数据，这个方法往往会大大减少搜索空间。

多重背包

有N种物品和一个体积为V的背包。第i种物品最多有num[i]件可用，每件体积是sizes[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包体积，且价值总和最大。

多重背包问题可以采取基于0-1背包的算法基础上增加一层循环搜索num[i]. 但这样的时间复杂度是O(NVC).

for (int i = 0; i < n; i++) { // items
    for (int k = 1; k <= num[i]; k++) {
        for (int j = size; j >= sizes[i]; j--) {
            vs[j] = Math.max(vs[j - sizes[i]] + values[i], vs[j]);
　　	  }
    }
}

多重背包问题其实包含0-1背包和完全背包，可以分类处理。

如果满足value[i]*num[i]>=size，这个时候就是完全背包问题, 而完全背包要比多重背包的复杂度低，是O(NV)。
如果满足num[i]=1就是0-1背包。

其他背包

混合背包: 如果将0-1、完全、多重混合起来，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。需要分类求解，判断是哪一种，然后分别给出循环和循环顺序，分别调用状态转换方程。

其他还有二维费用背包，依赖背包，分组背包…

Knapsack背包问题#

0-1背包#

完全背包#

完全背包的算法优化#

多重背包#

其他背包#