C++实现01背包问题的动态规划算法 |21xrx.com

C++实现01背包问题的动态规划算法

2023-07-11 05:33:13 深夜i -- --

C++ 01背包问题动态规划算法

01背包问题是一种经典的算法问题，也是动态规划算法的重要应用。它的基本思想是在给定一组物品和一个固定的背包容量下，选择一些物品放入背包中，使得物品的总价值最大，同时不超过背包的容量限制。

对于每个物品，我们可以选择将其放入背包中或者不放入。如果放入背包中，我们就需要减少背包的容量，同时增加物品的价值。如果不放入背包中，我们就不需要对背包容量进行修改。这种选择的过程可以用动态规划算法优雅地解决。

具体来说，我们可以通过一个二维的状态数组dp[i][j]来记录前i个物品中，背包容量为j时的最大价值。对于每个状态，我们有两种选择：选或者不选第i个物品。如果选择了第i个物品，则状态转移方程为：

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

如果不选择第i个物品，则状态转移方程为：

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

其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。根据这个状态转移方程，我们依次计算dp数组中的每个值，最终可以得到01背包问题的最终答案。

下面是使用C++语言实现01背包问题的动态规划算法的代码。


#include<bits/stdc++.h>
using namespace std;
int dp[105][105]; //状态数组，dp[i][j]表示前i个物品中，背包容量为j时的最大价值
int w[105], v[105]; //物品的重量和价值
int main(){
  int n, m; //物品的数量和背包的容量
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> w[i] >> v[i];
  }
  for(int i = 1; i <= n; i++){ //依次计算dp数组中的每个状态
    for(int j = m; j >= w[i]; j--){ //背包容量从大到小进行计算
      dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
    }
    for(int j = w[i] - 1; j >= 0; j--){ //不足w[i]的容量无法放入第i个物品
      dp[i][j] = dp[i - 1][j];
    }
  }
  cout << dp[n][m] << endl; //输出答案
  return 0;
}

通过这个简单的例子，我们可以看到动态规划算法的非常灵活和简便。它可以套用到各种不同的问题上，帮助我们高效地解决复杂的计算问题。

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

下一篇: C++索引的概念和作用是什么？

评论区

()

相似文章