题解 | #【模板】01背包#

题目链接

【模板】01背包

题目描述

你有一个容量为 $W$ 的背包和 $N$ 件物品。第 $i$ 件物品的体积为 $v_i$ ，价值为 $w_i$ 。每件物品只能使用一次。请对以下两种方案，分别求出能获得的最大总价值：

方案一: 不要求装满背包。
方案二: 要求最终恰好装满背包。如果不存在恰好装满的方案，则答案记为 0。

输入:

第一行两个整数 $N, W$ 。
接下来 $N$ 行，每行两个整数 $v_i, w_i$ 。

输出:

两行，分别对应两种方案的答案。

解题思路

这是一个典型的 0-1 背包问题，可以使用动态规划解决。题目要求的两种方案，其状态转移方程是相同的，但初始化的方式有着关键的不同。

我们将使用空间优化后的一维 DP 数组。

方案一：不要求装满背包

这是最标准的 0-1 背包问题。

定义状态: $dp[j]$ 表示在背包容量不超过 $j$ 的情况下，能获得的最大总价值。
状态转移方程: 对于每件物品 $i$ （体积为 $v$ ，价值为 $w$ ），我们要决定是否放入背包。
- 不放: 背包容量为 $j$ 时的最大价值仍然是 $dp[j]$ 。
- 放: 如果能放下（即 $j \ge v$ ），那么背包的剩余容量是 $j-v$ ，此时的最大价值是 $dp[j-v] + w$ 。我们取这两者中的最大值：dp[j] = max(dp[j], dp[j-v] + w)。为了在空间优化后保证 dp[j-v] 是上一轮（未放入物品 $i$ ）的状态，我们需要对容量 $j$ 进行从大到小的逆序遍历。
初始化: 我们将 dp 数组（大小为 $W+1$ ）全部初始化为 0。这代表着，在不放任何物品的情况下，任何容量的背包能获得的最大价值都是 0。
最终结果: 遍历完所有物品后，dp[W] 就是方案一的答案。

方案二：要求恰好装满背包

定义状态: $dp\_full[j]$ 表示在背包容量恰好为 $j$ 的情况下，能获得的最大总价值。
状态转移方程: 与方案一完全相同。
初始化: 这是与方案一的关键区别。
- dp_full[0] 初始化为 0。这表示容量为 0 的背包可以被“恰好装满”（即什么都不装），价值为 0。
- dp_full 数组的其他所有位置 (j > 0) 都应初始化为一个极小值（例如负无穷）。这表示在初始状态下，除了容量为 0 的背包，其他任何容量的背包都无法被恰好装满。只有当一个状态 dp_full[j-v] 是可达的（即值不为负无穷），它才能够去更新其他状态。
最终结果: 遍历完所有物品后，dp_full[W] 就是容量为 $W$ 时恰好装满的最大价值。如果 dp_full[W] 仍然是负无穷，说明不存在恰好装满的方案，按题意应输出 0。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = -1e18;

int main() {
    int n, w;
    cin >> n >> w;
    vector<int> v(n), val(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i] >> val[i];
    }

    // 方案一：不要求装满
    vector<long long> dp1(w + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = w; j >= v[i]; --j) {
            dp1[j] = max(dp1[j], dp1[j - v[i]] + val[i]);
        }
    }
    cout << dp1[w] << endl;

    // 方案二：要求恰好装满
    vector<long long> dp2(w + 1, INF);
    dp2[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = w; j >= v[i]; --j) {
            if (dp2[j - v[i]] > INF) { // 确保前一状态是可达的
                dp2[j] = max(dp2[j], dp2[j - v[i]] + val[i]);
            }
        }
    }

    if (dp2[w] < 0) { // 如果仍为负无穷（或一个很小的负数），则无解
        cout << 0 << endl;
    } else {
        cout << dp2[w] << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int[] v = new int[n];
        int[] val = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
            val[i] = sc.nextInt();
        }

        // 方案一：不要求装满
        long[] dp1 = new long[w + 1];
        for (int i = 0; i < n; i++) {
            for (int j = w; j >= v[i]; j--) {
                dp1[j] = Math.max(dp1[j], dp1[j - v[i]] + val[i]);
            }
        }
        System.out.println(dp1[w]);

        // 方案二：要求恰好装满
        long[] dp2 = new long[w + 1];
        Arrays.fill(dp2, -1); // 使用-1代表不可达，因为价值非负
        dp2[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = w; j >= v[i]; j--) {
                if (dp2[j - v[i]] != -1) { // 确保前一状态是可达的
                    dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + val[i]);
                }
            }
        }

        if (dp2[w] == -1) {
            System.out.println(0);
        } else {
            System.out.println(dp2[w]);
        }
    }
}

# 读取输入
n, w = map(int, input().split())
items = []
for _ in range(n):
    items.append(list(map(int, input().split())))

# --- 方案一：不要求装满 ---
dp1 = [0] * (w + 1)
for v, val in items:
    for j in range(w, v - 1, -1):
        dp1[j] = max(dp1[j], dp1[j - v] + val)
print(dp1[w])

# --- 方案二：要求恰好装满 ---
INF = -float('inf')
dp2 = [INF] * (w + 1)
dp2[0] = 0
for v, val in items:
    for j in range(w, v - 1, -1):
        if dp2[j - v] != INF: # 确保前一状态是可达的
            dp2[j] = max(dp2[j], dp2[j - v] + val)

if dp2[w] == INF:
    print(0)
else:
    print(dp2[w])

算法及复杂度

算法：动态规划（0-1背包，滚动数组优化）
时间复杂度： $\mathcal{O}(N \cdot W)$ - 两层循环，外层遍历物品，内层遍历背包容量。
空间复杂度： $\mathcal{O}(W)$ - 使用一维数组存储DP状态，符合题目要求。