21xrx.com
2024-11-22 06:45:28 Friday
登录
文章检索 我的文章 写文章
C++实现01背包问题的代码
2023-07-09 10:46:43 深夜i     --     --
C++ 01背包问题 实现 代码

C++是一种面向对象的编程语言,它可以实现各种计算机算法。本文将介绍如何使用C++编写一个解决01背包问题的代码。

01背包问题是指有一个背包,它的容量为C,现在有n个物品,第i个物品重量为w[i],价值为v[i]。在保证装入背包的物品总重量不超过C的前提下,如何选择装入背包的物品,可以使得物品的总价值最大。

为了解决这个问题,我们需要使用动态规划。动态规划是一种计算机算法,它通过将原问题分解为多个子问题来求解整个问题。

下面是C++实现01背包问题的代码:

#include

using namespace std;

int main() {

  int n, c;

  cin >> n >> c;

  int w[n], v[n];

  for (int i = 0; i < n; i++) {

    cin >> w[i] >> v[i];

  }

  int dp[n + 1][c + 1] = {0};

  for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= c; j++) {

      if (w[i - 1] > j) {

        dp[i][j] = dp[i - 1][j];

      } else {

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

      }

    }

  }

  cout << dp[n][c] << endl;

  return 0;

}

代码中,我们首先读入n、c、w和v数组,然后创建一个n+1行、c+1列的二维数组dp,其中dp[i][j]表示前i个物品中,容量为j的背包能装下的最大价值。

接着使用两个嵌套循环来遍历物品和背包容量,依次计算所有可能的情况。当物品重量大于当前背包容量时,则不能将该物品放入背包中,背包的最大价值与前i-1个物品的最大价值相同;当物品重量小于等于当前背包容量时,则可以将该物品放入背包中,背包的最大价值为前i-1个物品的最大价值和前i-1个物品中容量为j-w[i-1]的背包能装下的最大价值之和的较大值。

最后,输出dp[n][c]即为题目所求的最大价值。

总结

本文介绍了使用C++实现01背包问题的代码,其中使用了动态规划算法。在实际应用中,我们可以根据具体的问题场景进行代码优化和扩展,来更好地解决复杂的问题。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复