C++怎么实现一个动态规划算法_C++背包问题与DP状态转移方程

0-1背包问题通过动态规划求解，状态定义为dpi表示前i个物品在容量w下的最大价值，转移方程为dpi = max(dpi-1, dpi-1] + value[i-1])；C++实现采用二维数组填充DP表，可优化为一维数组从后往前更新，空间复杂度由O(nW)降为O(W)，适用于处理重叠子问题与最优子结构的最优化场景。

动态规划（Dynamic Programming，简称DP）是解决最优化问题的重要方法，尤其在处理具有重叠子问题和最优子结构的问题时非常高效。C++作为高性能编程语言，非常适合实现动态规划算法。下面以经典的0-1背包问题为例，讲解如何用C++实现动态规划，并推导状态转移方程。

什么是0-1背包问题？

给定n个物品，每个物品有重量weight[i]和价值value[i]，以及一个容量为W的背包。每件物品只能选择放入或不放入（即不能分割），目标是在不超过背包容量的前提下，使总价值最大。

DP状态定义与状态转移方程

关键在于设计合适的状态表示和递推关系。

状态定义：

立即学习“C++免费学习笔记（深入）”；

• 设dp[i][w]表示前i个物品，在背包容量为w时能获得的最大价值。

状态转移逻辑：

• 对于第i个物品（索引从1开始），有两种选择：
  • 不放入：则最大价值等于dp[i-1][w]
  • 放入（前提是w >= weight[i-1]）：则价值为dp[i-1][w - weight[i-1]] + value[i-1]
• 取两者最大值即可。

状态转移方程：

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])

Anakin

一站式 AI 应用聚合平台，无代码的AI应用程序构建器

下载

C++代码实现

以下是完整的C++实现，使用二维数组存储DP表：

#include 
#include 
#include 
using namespace std;
int knapsack(int W, vector& weight, vector& value) {
int n = weight.size();
// 创建DP表，初始化为0
vector> dp(n + 1, vector(W + 1, 0));
// 填充DP表
for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        // 不选第i个物品
        dp[i][w] = dp[i-1][w];
        // 如果能装下，尝试选择
        if (w >= weight[i-1]) {
            dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);
        }
    }
}

return dp[n][W];  // 返回最大价值
}
int main() {
vector weight = {2, 3, 4, 5};
vector value  = {3, 4, 5, 6};
int W = 8;
cout << "Maximum value: " << knapsack(W, weight, value) << endl;
return 0;
}

空间优化：使用一维数组
观察发现，每次更新只依赖上一行的数据。因此可以用一维数组优化空间复杂度到O(W)。
关键点：内层循环要从后往前遍历，避免覆盖还未使用的状态。
int knapsack_optimized(int W, vector& weight, vector& value) {
    int n = weight.size();
    vector dp(W + 1, 0);
for (int i = 0; i < n; i++) {
    for (int w = W; w >= weight[i]; w--) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}
return dp[W];
}

这种方法将空间从O(nW)降为O(W)，是实际应用中更常见的写法。
基本上就这些。掌握状态定义、转移方程推导和代码实现三步，就能应对大多数背包类DP问题。