C++动态规划解决0/1背包问题 |21xrx.com

C++动态规划解决0/1背包问题

2023-07-06 13:50:56 深夜i -- --

C++ 动态规划 0/1背包问题算法解决方案

在计算机科学中，背包问题是一种经典问题，常被用来描述一种优化问题：在有限的容量下，如何装入最多的价值？

0/1背包问题是其中一种类型，指的是每个物品只能选择放或者不放，而且容量是固定的。这个问题可以使用DP算法（动态规划）求解。

在C++中，可以通过以下代码实现0/1背包问题的动态规划算法。


#include<iostream>
#include<algorithm>
using namespace std;
int main() {
  int n, w, weight[1000], value[1000], dp[1001][1001];
  cin >> n >> w;
  for(int i = 1; i <= n; i++) {
    cin >> weight[i] >> value[i];
  }
  for(int i = 0; i <= n; i++) {
    dp[i][0] = 0;
  }
  for(int i = 0; i <= w; i++) {
    dp[0][i] = 0;
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= w; j++) {
      if(weight[i] <= j) {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
      }
      else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  cout << dp[n][w] << endl;
  return 0;
}

在这个例子中，首先输入物品数量n和背包容量w。然后输入每个物品的重量和价值，并在DP表中初始化边界值。接着进入两层循环，计算出DP表中每个元素的值。其中，DP表的i行j列表示前i个物品放在容量为j的背包中所得到的最大价值。动态规划的转移方程如下：

- 当第i个物品的重量小于等于j时，可以选择放入或者不放入。

- 放入：dp[i][j]=dp[i-1][j-weight[i]]+value[i]

- 不放：dp[i][j]=dp[i-1][j]

- 当第i个物品的重量大于j时，只能选择不放入。

最后输出dp[n][w]就是0/1背包问题的答案。

总之，C++的动态规划算法是解决小型和中型问题的一种非常有效的方法。有了这个算法，大家可以很好地解决0/1背包问题。

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

下一篇: 全国2022年计算机二级C++考试时期

评论区

()

相似文章