Knapsack

Knapsack Problems 背包问题

主要来源：九章：动态规划之背包问题专题教程

什么是背包问题？

简单来讲，你有一个背包，它的容量为V，你同时有若干个物品，它们有各自的体积和价值，将哪些物品装入背包可以使得它们的总体积和不超过背包的容量而总价值和最大？

我们把形如这样的一类与背包有关的问题称为背包问题。

有哪些背包问题？

1. 0 -1 背包问题 Backpack, Backpack II, Backpack V, Backpack VI, Backpack IX

2. 多重背包问题 Backpack VII, Backpack VIII

3. 完全背包问题 Backpack III, Backpack IV, Backpack X

0 -1 背包问题

问题概述

有 N 种物品，一个容量为 V 的背包，第 i 件物品的体积为 cap[i]，价值为 val[i]，求在不超过背包容量限制的情况下所能获得的最大物品价值和为多少？

一件物品要么不选，要么选，正好对应于 0-1 两个状态，所以我们一般把形如这样的背包问题称作 0-1 背包问题。

问题分析

对于 0-1 背包问题，我们一般选择利用动态规划进行求解

状态：

backpack[i][j] - 代表在前i件物品中选择若干件，这若干件物品的体积和不超过j的情况下，所能获得的最大物品价值和

状态转移方程：

backpack[i][j] = max(backpack[i−1][j], backpack[i−1][j − cap[i]] + val[i])

• 如果不将第 i 件物品放入背包，那么 backpack[i][j] 的值为 backpack[i - 1][j]；如果将第 i 件物品放入背包，那么 backpack[i][j] = backpack[i - 1][j - cap[i]] + val[i]。我们根据 backpack[i - 1][j] 和 backpack[i - 1][j - cap[i]] + val[i] 的大小选择放还是不放第 i 件物品。

backpack[0][j]=0, j∈[0,V]

• 在前 0 件物品中选择若干件，也就是一件都不选，此时无论物品的体积和为何值，物品价值和均为 0。

最后答案

为backpack[N][V]，即在前 N 件物品中选择若干件，这若干件物品的体积和不超过 V 的情况下，所能获得的最大物品价值和。

代码实现

for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= V; ++j) {
        backpack[i][j] = backpack[i - 1][j];
        if (j >= cap[i]) {
            backpack[i][j] = Math.max(backpack[i][j], backpack[i - 1][j - cap[i]] + val[i]);
        }
    }
}

复杂度分析

时间复杂度 O(NV)，空间复杂度 O(NV)。

滚动数组优化

观察到在计算 backpack[i][j] 时，我们只用到了backpack[i - 1][j] 和 backpack[i - 1][j - cap[i] 这两个数，并没有用到 backpack[i - 1][], backpack[i - 2][], ... 的信息，也就是 backpack[i][] 只和 backpack[i - 1][] 有关，那么我们只需要两个数组就够了。

for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= V; ++j) {
        int index = i & 1;
        backpack[index][j] = backpack[index ^ 1][j];
        if (j >= cap[i]) {
            backpack[index][j] = Math.max(backpack[index][j], backpack[index ^ 1][j - cap[i]] + val[i]);
        }
    }
}

空间复杂度从 O(NV) 降到了 O(V)。需要backpack[2][V]二维数组

一维数组优化

在第i层循环初f[j]存的相当于backpack[i - 1][j]的值。

在更新f[j]时，我们用到了f[j - cap[i]]，由于第二层循环倒序，所以f[j−cap[i]]未被更新，此时它代表backpack[i - 1][j - cap[i]]。所以f[j] = Math.max(f[j], f[j - cap[i]] + val[i])等价于backpack[i][j] = Math.max(backpack[i - 1][j], backpack[i - 1][j - cap[i]] + val[i])。

在第i层循环末f[j]存的相当于backpack[i][j]的值。

for (int i = 1; i <= N; ++i) {
    for (int j = V; j >= cap[i]; --j) {
        f[j] = Math.max(f[j], f[j - cap[i]] + val[i]);
    }
}

多重背包问题

问题概述

有 N 种物品，一个容量为 V 的背包，第 i 件物品的数量为 num[i]，体积为 cap[i]，价值为 val[i]，求在不超过背包容量限制的情况下所能获得的最大物品价值和为多少？

这个问题与 0-1 背包的区别在于，0-1 背包中每种物品有且只有一个，而多重背包中一种物品有nums[i]个。我们一般把形如这样的背包问题称作多重背包问题。

问题分析

求解这个问题一个简单的思路就是可以把它看成一个拥有 ∑ num[i]件物品的 0-1 背包问题。

Core Code

for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= V; ++j) {
        backpack[i][j] = backpack[i - 1][j];
        for (int k = 1; k <= num[i]; ++k) {
            if (j >= k * cap[i]) {
                backpack[i][j] = Math.max(backpack[i][j], backpack[i - 1][j - k * cap[i]] + k * val[i]);
            }
        }
    }
}

时间复杂度 O(V * ∑num[i])，空间复杂度O(N*V)。

一维数组优化：

for (int i = 1; i <= N; ++i) {
    for (int k = 1; k <= num[i]; ++k) {
        for (int j = V; j >= cap[i]; --j) {
            f[j] = Math.max(f[j], f[j - cap[i]] + val[i]);
        }
    }
}

时间复杂度 O(V * ∑num[i])，空间复杂度O(V)。

完全背包问题

问题概述

有 N 种物品，一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的体积为 cap[i]，价值为 val[i]。求在不超过背包的容量限制的情况下所能获得的最大总价值和为多少？

这个问题与 0-1 背包和多重背包都不同，前者每种物品只有1件，后者每种物品有num[i]件。而对于完全背包来讲，每种物品有无限件。

我们一般把形如这样的背包问题称作完全背包问题。

问题分析

问题转化：虽然题目声称每种物品都有无限件，但实际上每种物品最多有 V / cap[i] 件，因此这个问题相当于一个 num[i] = V / cap[i] 的多重背包问题。

Core Code

for (int i = 1; i <= N; ++i) {
    for (int k = 1; k * cap[i] <= V; ++k) {
        for (int j = V; j >= cap[i]; --j) {
            f[j] = Math.max(f[j], f[j - cap[i]] + val[i]);
        }
    }
}

例子：

给定 n 种具有大小 A[i] 和价值 V[i] 的物品（每个物品可以取用无限次）和一个大小为 m 的一个背包, 你可以放入背包里的最大价值是多少? 注意事项：你不能将物品分成小块, 选择的项目的总大小应小于或等于 m。

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        int n = A.length;
        int[] f = new int[m + 1];
        for (int i = 0; i < n; ++i) {
            for (int k = 1; k * A[i] <= m; ++k) {
                for (int j = m; j >= A[i]; --j) {
                    f[j] = Math.max(f[j], f[j - A[i]] + V[i]);
                }
            }
        }
        return f[m];
    }
}

时间复杂度 O(m∑ A[i] )，空间复杂度 O(m)。

时间复杂度优化

而且优化的方法十分简单，我们只需要将 j 的循环由逆向转变为正向即可。

由于同一种物品的个数无限，所以我们可以在任意容量 j的背包尝试装入当前物品，j从小向大枚举可以保证所有包含第 i种物品，体积不超过 j - A[i] 的状态被枚举到。

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        int n = A.length;
        int[] f = new int[m + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = A[i]; j <= m; ++j) {
                f[j] = Math.max(f[j], f[j - A[i]] + V[i]);
            }
        }
        return f[m];
    }
}

时间复杂度为 O(m)，空间复杂度为 O(m)

Reference

• 背包问题九讲 2.0 by Tianyi Cui
• mnmunknown 背包问题
• 九章：动态规划之背包问题专题教程
• 维基百科-背包问题
• 背包问题详解：01背包、完全背包、多重背包
• SegmentFault: [LintCode] Backpack I II III IV V VI [背包六问]