01背包问题的C++代码 |21xrx.com

01背包问题的C++代码

2023-07-08 14:52:45 深夜i -- --

01背包动态规划 C++ 算法代码

01背包问题是一种经典的动态规划问题，其解法被广泛应用于物品选择、装配、资源分配等领域。在这篇文章中，我们将介绍使用C++语言对01背包问题进行求解的方法，并提供相应的代码实现。

01背包问题描述

假设有一个包容量为C的背包，和一堆物品，每个物品有自己的体积和价值。我们的目标是选择一些物品放入背包中，使其价值最大，同时不能超过背包的容量。这就是经典的01背包问题。

01背包问题的思路

对于01背包问题，我们需要使用动态规划的思路来进行求解。假设我们已经处理了前i个物品，目前的背包容量为j，我们可以得到以下状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

其中dp[i][j]表示前i个物品，容量为j时的最大价值；w[i]表示第i个物品的体积；v[i]表示第i个物品的价值。

代码实现

下面是使用C++语言实现的01背包问题代码。


#include <iostream>
#include <vector>
using namespace std;
int knapsack(int n, int c, vector<int>& w, vector<int>& v) {
  vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= c; j++) {
      if (j < w[i]) {
        dp[i][j] = dp[i-1][j];
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
      }
    }
  }
  return dp[n][c];
}
int main() {
  int n = 4, c = 8;
  vector<int> w = {0, 2, 3, 4, 5};
  vector<int> v = {0, 3, 4, 5, 6};
  cout << knapsack(n, c, w, v) << endl;
  return 0;
}

代码中使用了动态规划的思路对01背包问题进行求解。首先定义了一个二维数组dp，用于保存最大价值信息。然后使用双重循环对每个物品和容量进行遍历，根据状态转移方程进行比较，并更新dp数组。最后返回数组中保存的最大价值。

总结

在这篇文章中，我们介绍了使用C++语言对01背包问题进行求解的方法，并提供了对应的代码实现。通过动态规划的思路，我们可以快速有效地解决这类物品选择、装配、资源分配等领域的问题，为实际生产生活提供有力支持。

上一篇: idea打包java可执行jar包

下一篇: "对C++的不赞成态度：它很烂"

评论区

()

相似文章