动态规划 | 小菜鸟

动态规划：从子问题到全局最优 —— 以背包问题为例

动态规划（Dynamic Programming，DP）是一种通过分解问题为重叠子问题，利用子问题的最优解逐步构建全局最优解的算法思想。它特别适合解决具有 “最优子结构” 和 “重叠子问题” 的问题，如背包问题、最长公共子序列、最短路径等。本文以经典的 0-1 背包问题为例，解析动态规划的核心原理、实现逻辑及优势。

动态规划的核心思想

核心特性

最优子结构：问题的最优解包含子问题的最优解。例如，“背包容量为 4 时的最大价值” 依赖于 “容量为 3 时的最大价值” 等子问题。
重叠子问题：不同的大问题可能包含相同的子问题，可通过存储子问题的解（“备忘录”）避免重复计算。
自底向上：从最小的子问题开始求解，逐步累积到原问题（与递归的 “自顶向下” 不同）。

与贪心算法的本质区别

贪心算法：每步选择局部最优，无回溯，可能得到近似解（如背包问题中仅选价值最高的物品）。
动态规划：通过枚举所有可能的子问题组合，确保得到全局最优解（如背包问题中考虑 “选或不选” 每个物品的所有情况）。

0-1 背包问题：动态规划的经典应用

问题重述

有 3 件物品和一个容量为 4 磅的背包，每件物品只能选一次（0-1 特性），求装入背包的最大价值：

物品	重量（磅）	价值（元）
吉他	1	1500
笔记本电脑	3	2000
音响	4	3000

动态规划解题步骤

定义状态（网格）

创建二维数组 v[i][j]，其中：

i 表示 “前 i 件物品”（i=0 表示无物品，i=1 表示吉他，i=2 表示吉他 + 笔记本电脑，i=3 表示所有物品）。
j 表示 “背包容量”（j=0 表示容量为 0，j=1 表示容量 1 磅，…，j=4 表示容量 4 磅）。
v[i][j] 的值表示 “前 i 件物品在容量 j 下的最大价值”。

初始化边界

当 i=0（无物品）：v[0][j] = 0（任何容量下价值都为 0）。
当 j=0（容量为 0）：v[i][0] = 0（无法装任何物品，价值为 0）。

状态转移方程（核心）

对于每个物品 i 和容量 j，有两种选择：

不选第 i 件物品：最大价值 = 前 i-1 件物品在容量 j 下的价值，即 v[i][j] = v[i-1][j]。
选第 i 件物品：若物品重量 ≤ 容量，则最大价值 = 物品价值 + 前 i-1 件物品在剩余容量（j - 物品重量）下的价值，即 v[i][j] = val[i-1] + v[i-1][j - weight[i-1]]。

最终取两种选择的最大值：

if 物品i的重量 > j（装不下）：
    v[i][j] = v[i-1][j]
else：
    v[i][j] = max(v[i-1][j], val[i-1] + v[i-1][j - weight[i-1]])

填充网格（计算子问题）

按行（物品）和列（容量）逐步计算 v[i][j] 的值：

i\j	1 磅	2 磅	3 磅	4 磅
0（无物品）	0	0	0	0
1（吉他）	1500	1500	1500	1500
2（吉他 + 笔记本）	1500	1500	2000	3500
3（所有物品）	1500	1500	2000	3500

解释：
- i=1, j=1：吉他重量 1≤1，选吉他，价值 1500。
- i=2, j=3：笔记本重量 3≤3，选笔记本（2000）比选吉他（1500）更优，故价值 2000。
- i=2, j=4：选笔记本（2000）+ 剩余容量 1 装吉他（1500），总 3500，优于不选的 1500。

回溯最优解（可选）

通过 path 数组记录每个状态下是否选择了第 i 件物品，最终回溯得到具体选择的物品（本例中为 “吉他 + 笔记本电脑”，总价值 3500）。

代码实现与解析

import java.util.Arrays;

public class KnapsackDP {
    public static void main(String[] args) {
        int[] weights = {1, 3, 4}; // 物品重量：吉他(1)、笔记本(3)、音响(4)
        int[] values = {1500, 2000, 3000}; // 对应价值
        String[] names = {"吉他", "笔记本电脑", "音响"};
        int capacity = 4; // 背包容量
        int n = values.length; // 物品数量

        // 状态数组：v[i][j]表示前i件物品在容量j下的最大价值
        int[][] v = new int[n + 1][capacity + 1];
        // 路径数组：记录选择的物品
        String[][] path = new String[n + 1][capacity + 1];
        for (String[] row : path) Arrays.fill(row, "");

        // 填充状态数组
        for (int i = 1; i <= n; i++) { // 遍历物品（i=1到n）
            for (int j = 1; j <= capacity; j++) { // 遍历容量（j=1到4）
                int itemWeight = weights[i - 1]; // 当前物品重量（i-1是因为物品从0开始）
                int itemValue = values[i - 1];   // 当前物品价值

                if (itemWeight > j) { // 装不下当前物品，继承上一状态
                    v[i][j] = v[i - 1][j];
                    path[i][j] = path[i - 1][j];
                } else { // 能装下，选或不选取最大值
                    int notTake = v[i - 1][j]; // 不选当前物品的价值
                    int take = itemValue + v[i - 1][j - itemWeight]; // 选当前物品的价值
                    if (take > notTake) {
                        v[i][j] = take;
                        // 记录选择：当前物品 + 剩余容量的选择
                        String prev = path[i - 1][j - itemWeight];
                        path[i][j] = names[i - 1] + (prev.isEmpty() ? "" : "+" + prev);
                    } else {
                        v[i][j] = notTake;
                        path[i][j] = path[i - 1][j];
                    }
                }
            }
        }

        // 输出结果
        System.out.println("最大价值：" + v[n][capacity] + "元");
        System.out.println("选择的物品：" + path[n][capacity]);
    }
}

输出：

最大价值：3500元
选择的物品：笔记本电脑+吉他

动态规划的优势与适用场景

优势

全局最优：通过枚举所有子问题组合，确保得到最优解（如背包问题中 3500 元优于贪心算法的 3000 元）。
效率高：利用重叠子问题的特性，通过一次计算存储结果，避免重复计算（时间复杂度 O (n×capacity)，远低于穷举的 O (2ⁿ)）。

适用场景

问题具有最优子结构：大问题的最优解依赖子问题的最优解（如最短路径、背包问题）。
存在重叠子问题：不同大问题共享相同的子问题（如斐波那契数列、最长公共子序列）。

总结

动态规划通过 “自底向上” 求解子问题，利用状态转移方程累积最优解，是解决多约束优化问题的强大工具。以 0-1 背包问题为例，它通过网格记录所有可能的子问题状态，最终找到全局最优解，这是贪心算法无法做到的。

掌握动态规划的关键在于：

定义清晰的状态（如 v[i][j] 的含义）；
推导出正确的状态转移方程（核心逻辑）；
合理初始化边界并填充状态表