解题思路

1. 二维循环

   • 定义 dp[i][j]：只用前 i 件物品、容量不超过 j 的最大价值。
   • 转移：当 j ≥ v[i] 时 dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + w[i])；否则 dp[i][j] = dp[i-1][j]。
   • 直观易懂，但空间 O(NV)。

2. 滚动数组优化

   • 观察到第 i 层只依赖第 i-1 层，压成一维 dp[j]。
   • 关键点：容量倒序（j = V..v[i]），避免同一物品重复使用： dp[j] = max(dp[j], dp[j - v[i]] + w[i])。
   • 时间 O(NV)，空间降为 O(V)。

3. 原地优化

   • “可达剪枝”：维护“可达最大容量” reachCap。处理第 i 件时，内层上界仅枚举到 end = min(V, reachCap + v[i])，跳过永不可达区间，减少无效更新。
   • “负无穷初始化”：令 dp[0]=0，其余 dp[j] 置为很小的负数（表示“不可达”）。转移前先判断 dp[j - v] 是否可达，代码更简洁安全。
   • 忽略无效物品：v[i] > V 可直接跳过。
   • 注意：此时 dp[j] 表示“恰好容量为 j 的最大价值”，答案为 max_{0≤j≤V} dp[j]。

复杂度分析

• 时间复杂度：O(N * V)。
• 空间复杂度：二维版 O(N * V)；滚动数组/原地优化版 O(V)。

代码实现

Python

# 最优化实现：一维 dp + 负无穷初始化 + 可达剪枝（reachCap）
import sys

def knapsack_01_optimized(n, V, vols, vals):
    NEG = -10**18  # 表示不可达
    dp = [NEG] * (V + 1)
    dp[0] = 0
    reach = 0  # 当前可达的最大容量

    for i in range(n):
        v, w = vols[i], vals[i]
        if v > V:
            continue  # 体积超过背包容量的物品直接跳过
        end = min(V, reach + v)  # 可达剪枝的上界
        # 倒序枚举，保证每件物品只用一次
        for j in range(end, v - 1, -1):
            if dp[j - v] != NEG:  # 只有前态可达才尝试转移
                cand = dp[j - v] + w
                if cand > dp[j]:
                    dp[j] = cand
        reach = end  # 更新当前可达的最大容量

    # 答案为不超过 V 的最大价值（恰好容量 j 的最大价值中的最大者）
    return max(dp)

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    N, V = data[0], data[1]
    vols, vals = [], []
    idx = 2
    for _ in range(N):
        v, w = data[idx], data[idx + 1]
        vols.append(v)
        vals.append(w)
        idx += 2
    print(knapsack_01_optimized(N, V, vols, vals))

if __name__ == "__main__":
    main()

Java

// 最优化实现：一维 dp + 负无穷初始化 + 可达剪枝（reachCap）
import java.util.*;

public class Main {
    // 外部函数：实现 0/1 背包（最优化版）
    static int knapsack01Optimized(int n, int V, int[] vols, int[] vals) {
        final int NEG = -1_000_000_000; // 不可达标记（远小于最大可能价值 1e6）
        int[] dp = new int[V + 1];
        Arrays.fill(dp, NEG);
        dp[0] = 0;

        int reach = 0; // 当前可达的最大容量
        for (int i = 0; i < n; i++) {
            int v = vols[i], w = vals[i];
            if (v > V) continue; // 无效物品跳过
            int end = Math.min(V, reach + v); // 可达剪枝上界
            for (int j = end; j >= v; j--) { // 倒序，保证每件物品只用一次
                if (dp[j - v] != NEG) {
                    int cand = dp[j - v] + w;
                    if (cand > dp[j]) dp[j] = cand;
                }
            }
            reach = end; // 更新可达上界
        }

        int ans = 0;
        for (int j = 0; j <= V; j++) ans = Math.max(ans, dp[j]);
        return ans;
    }

    // 主函数：读取输入并输出结果（ACM 风格）
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), V = sc.nextInt();
        int[] vols = new int[N], vals = new int[N];
        for (int i = 0; i < N; i++) {
            vols[i] = sc.nextInt();
            vals[i] = sc.nextInt();
        }
        System.out.println(knapsack01Optimized(N, V, vols, vals));
        sc.close();
    }
}

C++

// 最优化实现：一维 dp + 负无穷初始化 + 可达剪枝（reachCap）
#include <bits/stdc++.h>
using namespace std;

// 外部函数：实现 0/1 背包（最优化版）
int knapsack01Optimized(int n, int V, const vector<int>& vols, const vector<int>& vals) {
    const int NEG = -1000000000; // 不可达标记（足够小）
    vector<int> dp(V + 1, NEG);
    dp[0] = 0;

    int reach = 0; // 当前可达的最大容量
    for (int i = 0; i < n; ++i) {
        int v = vols[i], w = vals[i];
        if (v > V) continue; // 体积超过背包容量的物品跳过
        int end = min(V, reach + v); // 可达剪枝上界
        // 倒序枚举，避免同一物品重复使用
        for (int j = end; j >= v; --j) {
            if (dp[j - v] != NEG) {
                int cand = dp[j - v] + w;
                if (cand > dp[j]) dp[j] = cand;
            }
        }
        reach = end; // 更新可达上界
    }

    int ans = 0;
    for (int j = 0; j <= V; ++j) ans = max(ans, dp[j]);
    return ans;
}

// 主函数：读取输入并输出结果（ACM 风格）
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, V;
    if (!(cin >> N >> V)) return 0;
    vector<int> vols(N), vals(N);
    for (int i = 0; i < N; ++i) cin >> vols[i] >> vals[i];
    cout << knapsack01Optimized(N, V, vols, vals) << "\n";
    return 0;
}

题面描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

• 第一行两个整数 $N, V$，用空格隔开，分别表示物品数量和背包容量。
• 接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

• $0 < N, V \le 1000$
• $0 < v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8