网站导航
> 技术文档 > 【算法】动态规划：让我们“规划”最优解，别再乱选了！

【算法】动态规划：让我们“规划”最优解，别再乱选了！

网友: 技术文档 2025-09-03 04:11:09

一、什么是动态规划？——就是把问题“切割”成小块

1.1 动态规划是啥？

动态规划（Dynamic Programming，简称DP）看起来像一个高大上的名字，但其实它就是让你学会把大问题切割成一个个小问题。就像你想吃一块大蛋糕，但你不可能一次性把整个蛋糕塞进嘴里，对吧？你得切成一块块的，逐块享受。

简单来说，动态规划的核心思想就是：把复杂的问题分解成小问题，并且保存这些小问题的结果，下次用到的时候就直接拿来，避免重复劳动。

1.2 动态规划 vs 分治法

很多人搞不清楚动态规划和分治法的区别。其实它们之间的差别就像“站着”和“坐着”——其实差别很大但很容易混淆：

  • 分治法：把问题分成不重叠的子问题，每个子问题单独解决。

  • 动态规划：子问题是重叠的，已经解决过的小问题结果可以重复利用。

1.3 动态规划的基本步骤——你的“规划清单”

  1. 定义状态：明确每个子问题的解。

  2. 递推关系：找到子问题之间的关系，通过已解决的小问题来解决大问题。

  3. 边界条件：给定初始条件，通常是最小的问题答案。

  4. 保存中间结果：利用一个数组或者表格存储计算过的结果，避免重复计算。

二、经典问题：0-1背包问题——我是小偷，我要偷东西！

2.1 问题描述

想象你是一个“有品位”的小偷，站在一堆物品前，你的任务是：如何选择一些物品放进背包，使得背包的总价值最大，而又不超过背包的容量。

2.2 问题关键

你有几个物品，每个物品有重量和价值。你的背包容量是有限的，不能无限制地装东西，所以你需要在这些物品中做出选择。

示例数据：

  • 物品1：重量1，价值1500

  • 物品2：重量4，价值3000

  • 物品3：重量3，价值2000

  • 背包容量：4

你只能选择部分物品放进背包，目标是最大化背包的总价值。但是，记住：偷得过多，背包可能会爆炸！

三、解决思路——让我们来个“背包排序”

在动态规划中，我们通过构建一个二维数组 v[i][j] 来记录前 i 个物品在容量 j 背包下的最大价值。接着，通过递推公式，逐步计算出最优解。

3.1 递推公式

  • 如果当前物品的重量大于背包的剩余容量，那么不能选择该物品：
    v[i][j] = v[i-1][j]

  • 如果当前物品的重量小于等于剩余容量，我们有两种选择：

    1. 不选择当前物品：v[i][j] = v[i-1][j]

    2. 选择当前物品：v[i][j] = values[i-1] + v[i-1][j-weights[i-1]] 然后我们选择两者中的最大值。

四、代码实现——不如直接拿代码敲起来！

4.1 Java代码实现

import java.util.ArrayList;import java.util.List;public class KnapsackProblem { public static class KnapsackResult { int maxValue; List selectedItems; public KnapsackResult(int maxValue, List selectedItems) { this.maxValue = maxValue; this.selectedItems = selectedItems; } } public static KnapsackResult solveKnapsack(int[] weights, int[] values, int capacity) { int n = values.length; int[][] v = new int[n + 1][capacity + 1]; int[][] path = new int[n + 1][capacity + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j  j) {  v[i][j] = v[i - 1][j]; } else {  int newVal = values[i - 1] + v[i - 1][j - weights[i - 1]];  if (v[i - 1][j] < newVal) { v[i][j] = newVal; path[i][j] = 1;  } else { v[i][j] = v[i - 1][j];  } } } } List selectedItems = new ArrayList(); int i = n, j = capacity; while (i > 0 && j > 0) { if (path[i][j] == 1) { selectedItems.add(i); j -= weights[i - 1]; } i--; } return new KnapsackResult(v[n][capacity], selectedItems); } public static void main(String[] args) { int[] weights = {1, 4, 3}; int[] values = {1500, 3000, 2000}; int capacity = 4; KnapsackResult result = solveKnapsack(weights, values, capacity); System.out.println(\"最大价值: \" + result.maxValue); System.out.println(\"选择的物品: \" + result.selectedItems); for (int item : result.selectedItems) { System.out.printf(\"选取第%d个物品（重量%d，价值%d）\\n\", item, weights[item - 1], values[item - 1]); } }}

4.2 C++代码实现

#include #include #include using namespace std;struct KnapsackResult { int maxValue; vector selectedItems;};KnapsackResult solveKnapsack(vector& weights, vector& values, int capacity) { int n = values.size(); vector<vector> v(n + 1, vector(capacity + 1, 0)); vector<vector> path(n + 1, vector(capacity + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j  j) { v[i][j] = v[i - 1][j]; } else { int newVal = values[i - 1] + v[i - 1][j - weights[i - 1]]; if (v[i - 1][j] < newVal) {  v[i][j] = newVal;  path[i][j] = 1; } else {  v[i][j] = v[i - 1][j]; } } } } vector selectedItems; int i = n, j = capacity; while (i > 0 && j > 0) { if (path[i][j] == 1) { selectedItems.push_back(i); j -= weights[i - 1]; } i--; } return {v[n][capacity], selectedItems};}int main() { vector weights = {1, 4, 3}; vector values = {1500, 3000, 2000}; int capacity = 4; KnapsackResult result = solveKnapsack(weights, values, capacity); cout << \"最大价值: \" << result.maxValue << endl; cout << \"选择的物品: \"; for (int item : result.selectedItems) { cout << item << \" \"; } cout << endl; return 0;}

4.3 Python代码实现

class KnapsackResult: def __init__(self, max_value, selected_items): self.max_value = max_value self.selected_items = selected_itemsdef solve_knapsack(weights, values, capacity): n = len(values) v = [[0] * (capacity + 1) for _ in range(n + 1)] path = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, capacity + 1): if weights[i - 1] > j: v[i][j] = v[i - 1][j

五、执行过程演示——看到最终答案的过程

最终动态规划表（v[i][j] 代表前 i 个物品在容量 j 的背包下的最大价值）如下：

[0, 0, 0, 0, 0][0, 1500, 1500, 1500, 1500][0, 1500, 1500, 1500, 3000][0, 1500, 1500, 2000, 3500]

回溯路径：

从表格中我们可以看到，在最后一行（代表所有物品已考虑完）和最后一列（背包的容量）中，值为 3500，我们回溯这个路径找出选择的物品：

  • 选择了物品1（重量1，价值1500）

  • 选择了物品3（重量3，价值2000）

最终最大价值是 3500，选择的物品是物品1和物品3。

六、算法优化方向——让计算更高效

动态规划虽然能将指数级复杂度的问题转化为多项式复杂度，但它依然存在一些改进空间。

6.1 空间优化

    通常我们使用二维数组来存储中间结果，但如果仔细观察会发现，当前行的计算仅依赖于上一行的结果。因此，我们可以使用一维数组来优化空间复杂度。

6.2 记忆化搜索

    记忆化搜索是一种将递归问题转化为自顶向下的动态规划方法，通过缓存每个子问题的解来避免重复计算。

七、总结——让问题从“大”变“小”

    动态规划其实是一个非常强大的工具，它通过将复杂问题拆解为多个简单的小问题，并将中间结果保存起来，从而避免重复计算，大大提高了效率。理解并掌握动态规划，对于解决很多经典问题至关重要。现在你可以尝试一下其他经典的动态规划问题，比如最长公共子序列、分割等和子集等，通过更多的练习来巩固这一技术。

IMTI在线培训

网络标签：

相关问题