01背包问题

01背包问题是典型的动态规划问题。给定一个背包，容量为$\text{capacity}$，有$n$件物品，每件物品的重量为$w_i$，价值为$v_i$。问如何选择物品放入背包，使得背包中物品的总价值最大。

分析

为了便于分析，我们假设物品的重量和价值都是非负整数，并且物品的重量均不超过背包的容量。

穷举法

最朴素的想法是，我们可以枚举所有的方案，然后在满足背包容量的情况下，选择价值最大的方案。

这种方法的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11

function knapsack(capacity, n, weights, values):
    max_value = 0
    for each subset of items:
        total_weight = 0
        total_value = 0
        for each item in subset:
            total_weight += weights[item]
            total_value += values[item]
        if total_weight <= capacity and total_value > max_value:
            max_value = total_value
    return max_value

这里有比较明显的优化方式。如果前$i$件物品的总重量已经超过了背包的容量，那么这种方案就是无效的，我们可以直接终止后续计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function knapsack(capacity, n, weights, values):
    max_value = 0
    for each subset of items:
        total_weight = 0
        total_value = 0
        for each item in subset:
            total_weight += weights[item]
            if total_weight > capacity:
                total_value = 0
                break
            total_value += values[item]
        if total_value > max_value:
            max_value = total_value
    return max_value

一个小问题是如何枚举所有的子集。我们可以使用二进制的思想，将每一个整数看作一个$n$位的二进制数，其中第$j$位若为1，则表示第$j$个物品被选中；若为0，则表示第$j$个物品没有被选中。这样，我们可以通过枚举所有的整数$i$，来枚举所有的子集。下面是C语言的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int knapsack(int capacity, int n, int weights[], int values[]) {
    int max_value = 0;
    for (int i = 0; i < pow2(n); i++) {
        int total_weight = 0;
        int total_value = 0;

        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                total_weight += weights[j];
                if (total_weight > capacity) {
                    total_value = 0;
                    break;
                }
                total_value += values[j];
            }
        }

        if (total_value > max_value) {
            max_value = total_value;
        }
    }
    return max_value;
}

回溯法

上述的穷举法仍然存在优化空间。若前$i$件物品的总重量已经超过了背包的容量，那么后面的物品就无需考虑了。但是，穷举法仍然会枚举所有的情况，并且重复计算前$i$件物品的总重量。我们可以增加记忆化搜索，来避免重复计算；也可以保存无效方案的前缀，然后判断当前方案的前缀是否与某个无效方案的前缀相同。

为了达到这个目的，我们不妨考虑使用回溯法，这种想法更加直观。我们可以递归地考虑每一件物品，选择放入背包或者不放入背包。若将其放入背包，则判断已经放入背包的物品的总重量是否超过了背包的容量。若已经超过了背包容量，则直接终止；若没有超过，则继续递归地考虑下一件物品。若已经枚举完了所有的物品，就更新最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13

function knapsack(capacity, n, weights, values):
    max_value = 0
    function backtrack(i, current_weight, current_value):
        if current_weight > capacity:
            return
        if i == n:
            if current_value > max_value:
                max_value = current_value
            return
        backtrack(i + 1, current_weight, current_value)
        backtrack(i + 1, current_weight + weights[i], current_value + values[i])
    backtrack(0, 0, 0)
    return max_value

其中，第$10$行表示不选择第$i$件物品，第$11$行表示选择第$i$件物品。

用C语言可以实现上述伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int backtrack(int i, int current_weight, int current_value, int capacity, int n, int weights[], int values[]) {
    if (current_weight > capacity) {
        return INT_MIN;
    }
    if (i == n) {
        return current_value;
    }

    int value_without_item = backtrack(i + 1, current_weight, current_value, capacity, n, weights, values);
    int value_with_item = backtrack(i + 1, current_weight + weights[i], current_value + values[i], capacity, n, weights, values);

    return MAX(value_without_item, value_with_item);
}

int knapsack(int capacity, int n, int weights[], int values[]) {
    return MAX(backtrack(0, 0, 0, capacity, n, weights, values), 0);
}

不过，无论是穷举法还是回溯法，时间复杂度都是$O(2^n)$。对于大规模的问题是不可行的。

贪心法

还有一种符合直觉的想法是，我们可以按照单位重量的价值从大到小的顺序，依次选择物品放入背包。

1
2
3
4
5
6
7
8
9

function knapsack(capacity, n, weights, values):
    sort items by value per weight in descending order
    total_weight = 0
    total_value = 0
    for each item in items:
        if total_weight + item.weight <= capacity:
            total_weight += item.weight
            total_value += item.value
    return total_value

这种方法的时间复杂度是$O(n\log n)$。但这种方法并不一定能够得到最优解。例如，当背包容量为5时，考虑以下物品：

按照单位重量的价值从大到小的顺序，我们会选择物品$B$和$C$，总价值为$15$。但是，实际上，我们可以选择物品$A$和$C$，总价值为$17$。

为了构建这样的反例，以三件物品为例，我们可以先控制背包的容量和物品的重量，使得只能选择其中的两件物品。然后，我们可以构造出一件单位重量价值最高，但总价值最低的物品。这样，最优解中不会包含这件物品，但贪心法会选择这件物品。

动态规划

如果选择动态规划，我们有两种思考方式：一是当背包容量一定时，选择总价值最高的方案；二是当总价值一定时，选择总重量最低的方案。这里我们考虑第一种情况。下面我们先来说明01背包问题具有最优子结构的性质，以说明其能应用动态规划。

当我们考虑是否将第$i$件物品放入背包时，有两种选择：

1. 选择第$i$件物品：这时，我们需要考虑放入该物品后，背包的剩余容量变为$\text{capacity} - w_i$，我们接下来需要解决的问题就转化为在前$i-1$件物品中选择适合放入剩余容量的物品，从而最大化背包的价值。

2. 不选择第$i$件物品：在这种情况下，背包的容量保持为$\text{capacity}$，我们同样需要从前$i-1$件物品中选择物品以最大化背包的价值。

上述的两种选择可以将更大的问题分解为两个规模较小的子问题，分别对应于选择和不选择第$i$件物品的情形。每个子问题的解都是在已知当前选择的情况下，基于前一个物品的最优解进行的。

因此，01背包问题具有最优子结构的性质，可以应用动态规划。我们可以使用一个二维数组$dp$保存状态，其中$dp[i][j]$表示在前$i$件物品中，背包容量为$j$时的最大价值。状态转移方程为：

$$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)$$

初始时，我们可以将$dp$中的所有元素初始化为$0$，表示没有物品可以放入背包时的最大价值。

然后，我们可以按照物品的顺序，逐个考虑每一件物品，更新$dp$数组。最终，$dp[n][\text{capacity}]$即为所求的最大价值。下面的伪代码是自底向上版本的实现：

1
2
3
4
5
6

function knapsack(capacity, n, weights, values):
    dp = new int[n+1][capacity+1]
    for i from 1 to n:
        for j from weights[i] to capacity:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])
    return dp[n][capacity]

注意到这里的$j$是从$w_i$开始的，这是因为当$j < w_i$时，物品$i$是无法放入背包的。因此，我们可以直接跳过这种情况。

这种方法的时间复杂度是$O(n \cdot \text{capacity})$。下面是使用C语言实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int knapsack(int capacity, int n, int weights[], int values[]) {
    int dp[n + 1][capacity + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i - 1]) {
                dp[i][j] = MAX(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[n][capacity];
}

当然，我们注意到，对于每一个$i$，我们只需要考虑$dp[i-1][j]$和$dp[i-1][j-w_i]$，因此我们可以使用滚动数组来优化空间复杂度。

不过，在更新$dp[j]$的过程中，如果我们仍是从小到大更新$j$，那么$dp[j-w_i]$可能并不是我们希望的「前一个物品」的值，因为该值可能在本次循环中被更新过。这可能会导致一件物品被重复放入背包而导致错误的结果。因此，我们需要从大到小更新$j$。

1
2
3
4
5
6

function knapsack(capacity, n, weights, values):
    dp = new int[capacity+1]
    for i from 1 to n:
        for j from capacity to weights[i]:
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
    return dp[capacity]

下面是使用C语言实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12

int knapsack(int capacity, int n, int weights[], int values[]) {
    int dp[capacity + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int j = capacity; j >= weights[i - 1]; j--) {
            dp[j] = MAX(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
        }
    }

    return dp[capacity];
}

我们还可以通过带备忘录的自顶向下的方法来实现动态规划。这种方法的时间复杂度是$O(n \cdot \text{capacity})$，空间复杂度是$O(n \cdot \text{capacity})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function knapsack(capacity, n, weights, values):
    memo = new int[n+1][capacity+1]
    for i from 0 to n:
        for j from 0 to capacity:
            memo[i][j] = -1

    return knapsack_recursive(n, capacity, weights, values, memo)

function knapsack_recursive(i, capacity, weights, values, memo):
    if i == 0 or capacity == 0:
        return 0

    if memo[i][capacity] != -1:
        return memo[i][capacity]

    if weights[i-1] > capacity:
        memo[i][capacity] = knapsack_recursive(i-1, capacity, weights, values, memo)
    else:
        choose_item = knapsack_recursive(i-1, capacity - weights[i-1], weights, values, memo) + values[i-1]
        skip_item = knapsack_recursive(i-1, capacity, weights, values, memo)
        memo[i][capacity] = max(choose_item, skip_item)

    return memo[i][capacity]

下面是使用C语言实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int knapsack_recursive(int i, int capacity, int* weights, int* values, int** memo) {
    if (i == 0 || capacity == 0) {
        return 0;
    }

    if (memo[i][capacity] != -1) {
        return memo[i][capacity];
    }

    if (weights[i - 1] > capacity) {
        memo[i][capacity] = knapsack_recursive(i - 1, capacity, weights, values, memo);
    } else {
        int choose_item = knapsack_recursive(i - 1, capacity - weights[i - 1], weights, values, memo) + values[i - 1];
        int skip_item = knapsack_recursive(i - 1, capacity, weights, values, memo);
        memo[i][capacity] = (choose_item > skip_item) ? choose_item : skip_item;
    }

    return memo[i][capacity];
}

int knapsack(int capacity, int n, int* weights, int* values) {
    int memo[n + 1][capacity + 1];
    memset(memo, -1, sizeof(memo));

    int result = knapsack_recursive(n, capacity, weights, values, memo);
    return result;
}

变体

背包容量极大

先前提到的动态规划，是在背包容量一定时，选择总价值最高的方案。但若背包容量极大，而物品数量不多，我们直接使用这种方式，会导致时间和空间复杂度都很高。这时，我们可以采用另一种思考方式，即考察当背包价值一定的情况下，所需要的最小重量。

与先前的思考方式相同。对于第$i$件物品，我们可以选择放入背包或者不放入背包。若选择放入背包，则我们需要考虑当背包价值为$j-v_i$时，所需要的最小重量。若不放入背包，则我们需要考虑当背包价值为$j$时，所需要的最小重量。我们可以使用一个二维数组$dp$保存状态，其中$dp[i][j]$表示，在前$i$件物品中，背包价值为$j$时，所需要的最小重量。状态转移方程为：

$$dp[i][j]=min(dp[i-1][j],dp[i-1][j-v_i]+w_i)$$

由于$dp[i][j]$的值只与$dp[i-1][j]$和$dp[i-1][j-v_i]$有关，我们同样可以使用滚动数组来优化空间复杂度。其中$dp[j]$表示背包价值为$j$时，所需要的最小重量。状态转移方程为：

$$dp[j]=min(dp[j],dp[j−v_i]+w_i)$$

初始化时，我们可以将$dp[0]$设置为$0$，表示背包价值为$0$时，所需要的最小重量为$0$。其他的$dp[j]$可以设置为一个较大的值，例如$+\infty$，表示无法达到该价值。

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

function knapsack(capacity, n, weights, values):
    dp = new int[sum(values)+1]
    for i from 1 to sum(values):
        dp[i] = INT_MAX
    dp[0] = 0
    for i from 1 to n:
        for j from sum(values) to values[i]:
            if dp[j-values[i]] != INT_MAX:
                dp[j] = min(dp[j], dp[j-values[i]] + weights[i])
    for i from sum(values) to 0:
        if dp[i] <= capacity:
            return i

下面是使用C语言实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int knapsack(int capacity, int n, int weights[], int values[]) {
    int sum_values = 0;
    for (int i = 0; i < n; i++) {
        sum_values += values[i];
    }

    int dp[sum_values + 1];
    for (int i = 1; i <= sum_values; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = sum_values; j >= values[i]; j--) {
            if (dp[j - values[i]] != INT_MAX) {
                dp[j] = MIN(dp[j], dp[j - values[i]] + weights[i]);
            }
        }
    }

    for (int i = sum_values; i >= 0; i--) {
        if (dp[i] <= capacity) {
            return i;
        }
    }
}

可选免费物品

有时会遇到这样的问题：在选择物品放入背包时，其中最多$k$件可以作为免费物品，即这些物品的重量可视为$0$。为了使总重量尽可能低，我们希望将重量较高的物品作为免费项，而重量较低的物品作为付费项。我们可以证明：存在最优解，使得

• 付费物品均出现在某个分界点之前，
• 免费物品均出现在这个分界点之后。

简单解释：假设某最优解中有一件免费物品的重量比某件付费物品还低，那么交换二者，花费不增加（甚至会减少），价值不变，从而得到另一解。故我们可以假设在最优方案中，付费部分全来自于物品中较便宜的一部分，而免费部分全来自于较贵的一部分。

因此，可以先将物品的质量从小到大排序，然后引入「分界点」$r$，将物品分为两部分：

• 前$r$件物品作为付费候选，
• 后$n-r$件物品作为免费候选。

记：

• $paid[r]$：在前$r$件物品中，通过01背包（花费不超过$\text{capacity}$）所能获得的最大总价值；
• $free[r]$：在后$n-r$件物品中贪心选取最多$k$件物品的总价值。

最终答案为：

$max\{ paid[r] + free[r] \}$，其中$r$从$0$到$n$都需要枚举。