c++中如何实现动态规划背包问题_c++动态规划背包问题实现方法-C++-PHP中文网

c++中如何实现动态规划背包问题_c++动态规划背包问题实现方法

尼克

发布： 2025-10-03 11:38:02

原创

509人浏览过

动态规划解决0-1背包问题通过状态转移方程dpi=max(dpi-1, dpi-1]+value[i])避免重复计算，使用二维数组实现后可优化为一维数组，从后往前更新避免覆盖，空间复杂度由O(nW)降为O(W)，关键在于状态定义和逆序遍历。

c++中如何实现动态规划背包问题_c++动态规划背包问题实现方法

动态规划解决背包问题在C++中非常常见，尤其适用于0-1背包、完全背包等场景。核心思想是通过状态转移方程避免重复计算，提升效率。下面以经典的0-1背包问题为例，介绍实现方法。

问题描述

有n个物品，每个物品有重量weight[i]和价值value[i]，给定一个承重为W的背包，求能装入的最大总价值，每件物品最多选一次。

定义状态与转移方程

使用二维数组dp[i][w]表示前i个物品在承重不超过w时的最大价值：

若不选第i个物品：dp[i][w] = dp[i-1][w]
若选择第i个物品（前提是w ≥ weight[i]）：dp[i][w] = dp[i-1][w-weight[i]] + value[i]

状态转移方程为：

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

C++实现代码（二维数组版本）

这是最直观的实现方式：

#include <iostream>
#include <vector>
using namespace std;
<p>int knapsack(int n, int W, vector<int>& weight, vector<int>& value) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));</p><pre class='brush:php;toolbar:false;'>for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        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];

登录后复制

}

Symanto Text Insights

基于心理语言学分析的数据分析和用户洞察

查看详情

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

int main() { int n = 4, W = 8; vector<int> weight = {2, 3, 4, 5}; vector<int> value = {3, 4, 5, 6};

cout << "最大价值: " << knapsack(n, W, weight, value) << endl;
return 0;

登录后复制

}

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

空间优化：一维数组实现

观察发现，dp[i][w]只依赖于dp[i-1][...]，因此可用一维数组滚动更新，从后往前遍历避免覆盖：

int knapsack_optimized(int n, int W, vector<int>& weight, vector<int>& value) {
    vector<int> dp(W + 1, 0);
<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];

登录后复制

}

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

这种方法将空间复杂度从O(nW)降到O(W)，是实际应用中的常用写法。

基本上就这些。掌握状态定义和逆序更新是一维优化的关键。

以上就是c++++中如何实现动态规划背包问题_c++动态规划背包问题实现方法的详细内容，更多请关注php中文网其它相关文章！