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

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

2023-07-04 14:10:47 深夜i -- --

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

01背包问题是指在有限的容量内，选择不同重量和价值的物品，使得装入背包的物品总价值最大。C++语言的优异性能让其成为解决此类问题的重要工具，下面我们来看一下C++实现的01背包问题代码。

首先，我们需要定义物品的结构体，包含物品的重量和价值：


struct item
  int weight; // 物品重量
  int value; // 物品价值
;

然后，我们需要输入背包的容量和物品的数量：


int capacity; // 背包容量
int num_items; // 物品数量
cin >> capacity >> num_items;

接着，我们需要定义一个二维数组dp，表示当前状态下的最大价值：


int dp[num_items + 1][capacity + 1];
memset(dp, 0, sizeof(dp)); // 初始化为0

然后，我们需要输入每个物品的重量和价值：


vector<item> items; // 物品数组
items.push_back(item0); // 空物品
for (int i = 1; i <= num_items; i++) {
  int weight, value;
  cin >> weight >> value;
  items.push_back(item value);
}

接下来，我们可以使用动态规划的方法来解决01背包问题。状态转移方程为：


dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

其中，dp[i][j] 表示考虑前i个物品，在背包容量为j时的最大价值。weight[i] 和 value[i] 分别表示第i个物品的重量和价值。

最终，我们可以输出最大价值：


cout << dp[num_items][capacity] << endl;

完整的代码如下：


#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct item
  int weight; // 物品重量
  int value; // 物品价值
;
int main() {
  int capacity; // 背包容量
  int num_items; // 物品数量
  cin >> capacity >> num_items;
  int dp[num_items + 1][capacity + 1];
  memset(dp, 0, sizeof(dp)); // 初始化为0
  vector<item> items; // 物品数组
  items.push_back(item0); // 空物品
  for (int i = 1; i <= num_items; i++) {
    int weight, value;
    cin >> weight >> value;
    items.push_back(itemweight);
  }
  for (int i = 1; i <= num_items; i++) {
    for (int j = 1; j <= capacity; j++) {
      if (j < items[i].weight) {
        dp[i][j] = dp[i-1][j];
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-items[i].weight]+items[i].value);
      }
    }
  }
  cout << dp[num_items][capacity] << endl;
  return 0;
}

以上就是C++实现的01背包问题代码，希望能对您有所帮助。

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

下一篇: VC++6.0能否编写C++代码？

评论区

()

相似文章