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

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

下次还敢

发布： 2025-12-01 16:26:43

原创

420人浏览过

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

c++怎么实现一个动态规划算法_c++背包问题与dp状态转移方程

动态规划（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])

Word-As-Image for Semantic Typography

文字变形艺术字、文字变形象形字

查看详情

C++代码实现

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
<p>int knapsack(int W, vector<int>& weight, vector<int>& value) {
int n = weight.size();
// 创建DP表，初始化为0
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));</p><pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">// 填充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<int> weight = {2, 3, 4, 5}; vector<int> 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<int>& weight, vector<int>& value) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);
<pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">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问题。

以上就是C++怎么实现一个动态规划算法_C++背包问题与DP状态转移方程的详细内容，更多请关注php中文网其它相关文章！