c++怎么用动态规划解决0-1背包问题_c++实现0-1背包的动态规划算法-C++-PHP中文网

c++怎么用动态规划解决0-1背包问题_c++实现0-1背包的动态规划算法

尼克

发布： 2025-11-29 17:33:49

原创

154人浏览过

0-1背包问题通过动态规划求解，使用二维数组dpi表示前i个物品在容量w下的最大价值，状态转移方程为dpi = max(dpi-1, dpi-1] + value[i])；可通过滚动数组优化为空间复杂度更低的一维形式，时间复杂度O(nW)，适用于中小规模问题。

c++怎么用动态规划解决0-1背包问题_c++实现0-1背包的动态规划算法

0-1背包问题是经典的动态规划问题。给定n个物品，每个物品有重量和价值，一个背包有最大承重限制，要求在不超过背包容量的前提下，选择物品使得总价值最大，每种物品只能选一次。

动态规划思路

使用二维数组 dp[i][w] 表示前i个物品在背包容量为w时能获得的最大价值。

状态转移方程：

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

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

其中：

Writer

企业级AI内容创作工具

176

查看详情

如果不选第i个物品：dp[i][w] = dp[i-1][w]
如果选第i个物品（前提是weight[i] ≤ w）：dp[i][w] = dp[i-1][w-weight[i]] + value[i]

C++实现代码

#include <iostream>
#include <vector>
using namespace std;
<p>int knapsack(int W, vector<int>& weight, vector<int>& value) {
int n = weight.size();
// 创建二维DP表
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));</p><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];
        // 如果能装下第i个物品，尝试选择它
        if (weight[i-1] <= w) {
            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> value = {60, 100, 120}; vector<int> weight = {10, 20, 30}; int W = 50; cout << "最大价值: " << knapsack(W, weight, value) << endl; return 0; }

优化空间复杂度（滚动数组）

可以将二维DP优化为一维数组，减少空间使用。

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;'>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)，适合中小规模问题。

以上就是c++++怎么用动态规划解决0-1背包问题_c++实现0-1背包的动态规划算法的详细内容，更多请关注php中文网其它相关文章！