01背包问题 · 动态规划演示

📥 输入数据

背包容量 W

物品（重量, 价值），每行一个

选择路径关键比较

① 二维DP（标准解法）

// 二维动态规划
// dp[i][j] = 前 i 个物品, 容量 j 的最大价值
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        if (j < w[i])
            dp[i][j] = dp[i-1][j];      // 装不下
        else
            dp[i][j] = max(dp[i-1][j],          // 不取
                           dp[i-1][j-w[i]] + v[i]); // 取
    }
}

点击「运行」查看结果

② 一维DP（滚动数组优化）

// 一维滚动数组
// dp[j] = 容量 j 的最大价值
// ⚠ 容量要逆序遍历！
for (int i = 1; i <= n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}

点击「运行」查看结果

③ 完全背包（无限次取同一物品）

// 完全背包 - 无限取同一物品
// ⚠ 容量要正序遍历（允许反复加同一物品）
for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= W; j++) {
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}

点击「运行」查看结果

📊 三组测试数据与输出

测试 ① 基础

容量: 10
物品:
(2,3) (3,4) (4,5) (5,6)
→ 二维: dp[4][10] = 12
→ 一维: dp[10] = 12
→ 完全: dp[10] = 15 (取3个5,6 + 1个2,3)

测试 ② 边界

容量: 8
物品:
(1,1) (2,2) (3,5) (5,10)
→ 二维: dp[4][8] = 13
→ 一维: dp[8] = 13
→ 完全: dp[8] = 16 (取1个5,10 + 1个3,5)

测试 ③ 大容量

容量: 14
物品:
(3,7) (4,9) (6,12) (2,4) (5,11)
→ 二维: dp[5][14] = 27
→ 一维: dp[14] = 27
→ 完全: dp[14] = 33 (取3个4,9 + 1个2,4)

🔗 参考资料

01背包动态规划状态转移图解：

🎒 01背包问题 · 动态规划演示

📥 输入数据

① 二维DP（标准解法）

② 一维DP（滚动数组优化）

③ 完全背包（无限次取同一物品）

📊 三组测试数据与输出

测试 ① 基础

测试 ② 边界

测试 ③ 大容量

🔗 参考资料