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

C++实现01背包问题代码

2023-06-22 06:10:36 深夜i -- --

C++ 01背包问题实现代码

01背包问题是一种经典的动态规划问题，它已被广泛应用于各种领域。在本文中，我们将介绍如何使用C++实现01背包问题的解法。

1. 什么是01背包问题？

01背包问题是一种经典的动态规划问题，可以通俗地理解为，有一个给定容量的背包，要求在有限的物品中选择一部分装入背包，使得装入的物品总价值最大。

具体来说，假设背包容量为C，物品数量为N，每个物品有自己的价值和重量，分别为v和w，需要决定哪些物品装入背包，则可以通过以下的动态规划状态转移方程解决这个问题：

- 如果当前背包容量小于等于0，那么背包中的价值为0：f(0, j) = 0 (0≤j≤C)

- 如果当前待装物品数量为0，那么背包中的价值为0：f(i, 0) = 0 (1≤i≤N)

- 如果背包容量大于当前物品的重量，那么可以选择把当前物品装进背包，也可以选择不装进背包：

f(i, j) = max{f(i-1, j), f(i-1, j-w[i])+v[i]}

- 如果背包容量小于当前物品的重量，那么不可能把当前物品装进背包里：

f(i, j) = f(i-1, j)

2. C++代码实现

下面是一个简单的C++代码，实现了01背包问题的求解。我们使用了一个二维数组f[i][j]来保存动态规划的状态转移方程，其中f[i][j]表示在前i个物品中选择一些物品，使得它们的总重量不超过j的情况下，最终所能得到的最大价值。


#include<bits/stdc++.h>
using namespace std;
int n, m, f[105][105], w[105], v[105];
int main() {
  ios :: sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i];
  for (int i = 1; i <= n; ++i) {
    for (int j = m; j >= w[i]; --j) {
      f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+v[i]);
    }
  }
  cout << f[n][m] << endl;
  return 0;
}

在以上代码中，我们首先定义了一个二维数组f[i][j]，其中i表示前i个物品，j表示背包的容量。然后通过两重循环来进行状态转移方程的计算，最终输出f[n][m]，即前n个物品中选择一些物品，使得它们的总重量不超过m的情况下，最终所能得到的最大价值。

到此，C++实现01背包问题的代码已经讲解完毕。希望本文能够对您有所帮助，如果您有任何问题或建议，欢迎在评论区留言。

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

下一篇: C++ 多线程（Thread）

评论区

()

相似文章