阅读量:0
目录
动态规划（Dynamic Programming, DP）是计算机科学中一种解决复杂问题的高效方法。通过将问题分解成更小的子问题并存储其结果，动态规划避免了重复计算，从而显著提高了效率。本文将详细介绍动态规划的基本概念，并以经典的0/1背包问题为例，展示如何应用动态规划进行求解。
一、动态规划简介
动态规划是一种优化技术，适用于解决具有重叠子问题和最优子结构性质的问题。其核心思想是通过记录已解决的子问题的结果，避免重复计算，从而提高算法效率。
动态规划的步骤通常包括：
- 定义子问题：将原问题分解为更小的子问题。
- 确定状态：定义表示子问题的状态变量。
- 状态转移方程：找到状态之间的递推关系。
- 初始条件和边界情况：设定初始状态的值。
- 计算最终结果：根据递推关系和初始条件计算出原问题的解。
二、0/1背包问题概述
0/1背包问题是组合优化中的经典问题之一，其定义如下：
给定一个容量为 W的背包，以及 n个物品，每个物品有一个重量 wi和价值 vi。在保证总重量不超过背包容量的前提下，如何选择物品使得总价值最大？
与之不同的是，每个物品只能选择一次（即0/1选择），而不是无限制地选择（完全背包问题）。
三、动态规划解决0/1背包问题
1. 定义子问题
设 dp[i][j]表示前 iii 个物品在背包容量为 jjj 时的最大总价值。目标是求 dp[n][W]。
2. 确定状态
状态 dp[i][j]dp[i][j]dp[i][j] 的值可以通过以下方式递推得到：
- 如果不选择第 i个物品，则 dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j]dp[i][j]=dp[i−1][j]。
- 如果选择第 i个物品，则 dp[i][j]=dp[i−1][j−wi]+vi，前提是j ≥ wi。
因此，状态转移方程为： dp[i][j]=max(dp[i−1][j],dp[i−1][j−wi]+vi)
3. 初始条件和边界情况
对于初始条件，当没有物品或背包容量为0时，总价值均为0：
dp[0][j] = 0 对于0≤j≤W
dp[i][0] = 0 对于0≤i≤n
4. 计算最终结果
通过自底向上填充DP表格，最终结果即为 dp[n][W]。
5. 代码实现
以下是C++实现，代码中包含了详细的解释：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack(const vector<int>& weights, const vector<int>& values, int W) {
int n = weights.size();
// 创建一个二维数组 dp，大小为 (n+1) x (W+1)，并初始化为 0
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// 填充 dp 表格
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
if (weights[i-1] <= w) {
// 如果可以放入当前物品，选择放或不放，取最大值
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
} else {
// 如果不能放入当前物品，直接取前 i-1 个物品的最大值
dp[i][w] = dp[i-1][w];
}
}
}
// 最终结果是 dp[n][W]，即考虑所有物品在最大重量 W 时的最大价值
return dp[n][W];
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
int W = 5;
cout << "Maximum value in Knapsack = " << knapsack(weights, values, W) << endl;
return 0;
}
6. 空间优化
上述实现的时间复杂度为 O(nW)，空间复杂度同样为 O(nW)。可以通过空间优化将空间复杂度降至 O(W)。这是因为在计算 dp[i][j]时，只需要参考 dp[i−1][j]和 dp[i−1][j−wi] 两个状态，因此可以使用一维数组进行优化。
优化后的实现如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack_optimized(const vector<int>& weights, const vector<int>& values, int W) {
int n = weights.size();
vector<int> dp(W + 1, 0);
// 通过一维数组优化空间复杂度
for (int i = 0; i < n; ++i) {
for (int w = W; w >= weights[i]; --w) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
int W = 5;
cout << "Maximum value in Knapsack = " << knapsack_optimized(weights, values, W) << endl;
return 0;
}
四、例题讲解
例题1：基础例题
题目：给定一个背包的容量为 5，以及 4 个物品，每个物品的重量和价值分别为 {2, 3, 4, 5} 和 {3, 4, 5, 6}。求如何选择物品使得总价值最大。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack(const vector<int>& weights, const vector<int>& values, int W) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// 填充 dp 表格
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
if (weights[i-1] <= w) {
// 如果可以放入当前物品，选择放或不放，取最大值
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
} else {
// 如果不能放入当前物品，直接取前 i-1 个物品的最大值
dp[i][w] = dp[i-1][w];
}
}
}
return dp[n][W];
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
int W = 5;
cout << "Maximum value in Knapsack = " << knapsack(weights, values, W) << endl;
return 0;
}
代码解释：
- 初始化
dp数组，用于存储子问题的解。 - 双重循环填充
dp表格，其中dp[i][w]表示前i个物品在容量为w时的最大价值。 - 根据物品是否放入背包来更新
dp[i][w]的值。 - 最后返回
dp[n][W]，即为最大总价值。
例题2：路径恢复
题目：求解背包问题的同时，找出选择的物品。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int, vector<int>> knapsack_with_items(const vector<int>& weights, const vector<int>& values, int W) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
vector<vector<bool>> keep(n + 1, vector<bool>(W + 1, false));
// 填充 dp 表格并记录是否选择物品
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
if (weights[i-1] <= w) {
if (dp[i-1][w] < dp[i-1][w - weights[i-1]] + values[i-1]) {
dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1];
keep[i][w] = true;
} else {
dp[i][w] = dp[i-1][w];
}
} else {
dp[i][w] = dp[i-1][w];
}
}
}
// 回溯找出选择的物品
int w = W;
vector<int> items;
for (int i = n; i >= 1; --i) {
if (keep[i][w]) {
items.push_back(i-1);
w -= weights[i-1];
}
}
return {dp[n][W], items};
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
int W = 5;
auto result = knapsack_with_items(weights, values, W);
cout << "Maximum value in Knapsack = " << result.first << endl;
cout << "Items included: ";
for (int i : result.second) {
cout << i << " ";
}
cout << endl;
return 0;
}
代码解释：
- 在
dp数组外增加一个keep数组，用于记录是否选择某个物品。 - 在填充
dp表格时，更新keep数组以记录选择情况。 - 通过回溯
keep数组，找出选择的物品并存储在items数组中。 - 最后返回最大总价值和选择的物品列表。
例题3：扩展问题
题目：考虑更多约束条件，如物品的体积和背包的体积限制。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int weight;
int volume;
int value;
};
int knapsack_with_volume(const vector<Item>& items, int W, int V) {
int n = items.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(W + 1, vector<int>(V + 1, 0)));
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
for (int v = 0; v <= V; ++v) {
if (items[i-1].weight <= w && items[i-1].volume <= v) {
dp[i][w][v] = max(dp[i-1][w][v], dp[i-1][w - items[i-1].weight][v - items[i-1].volume] + items[i-1].value);
} else {
dp[i][w][v] = dp[i-1][w][v];
}
}
}
}
return dp[n][W][V];
}
int main() {
vector<Item> items = {
{2, 3, 4},
{3, 4, 5},
{4, 5, 6},
{5, 6, 7}
};
int W = 5;
int V = 7;
cout << "Maximum value in Knapsack = " << knapsack_with_volume(items, W, V) << endl;
return 0;
}
代码解释：
- 定义
Item结构体，包含物品的重量、体积和价值。 - 初始化
dp三维数组，用于存储子问题的解。 - 三重循环填充
dp表格，其中dp[i][w][v]表示前i个物品在重量为w和体积为v时的最大价值。 - 根据物品是否放入背包来更新
dp[i][w][v]的值。 - 最后返回
dp[n][W][V]，即为最大总价值。
五、总结
通过本文的详细解析和多个例题的讲解，我们可以深入理解动态规划及其在0/1背包问题中的应用。从定义子问题、确定状态、推导状态转移方程、设定初始条件，到计算最终结果，动态规划提供了一种系统而高效的解决问题的思路。
掌握动态规划的基本原理和应用技巧，不仅能解决背包问题，还能扩展到其他领域，如字符串匹配、序列比对、路径规划等。希望本文能够帮助读者更好地理解和应用动态规划，提升解决复杂问题的能力。
