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

C++实现01背包问题

2023-07-05 01:09:11 深夜i -- --

C++ 01背包问题实现

01背包问题是一个经典的算法问题，可以用来解决各种实际问题。在这个问题中，我们有$n$个物品和一个背包，背包的最大容量为$W$。每个物品有重量$w_i$和价值$v_i$。我们的目标是选择一些物品放入背包中，使得它们的总重量不超过背包容量，且总价值最大。

C++语言是一种十分流行的编程语言，具有许多丰富的类库和工具，可以帮助我们更轻松地解决问题。下面，我们将介绍如何使用C++编写一个简单的01背包问题算法。

1. 定义问题

我们首先需要定义一个结构体，用来表示每个物品的属性：重量和价值。


struct Item
  int weight;
  int value;
;

2. 定义函数

接下来，我们定义一个函数，用来计算在给定的物品集合和背包容量下，能够取得的最大价值。这里我们称之为$knapsack$函数。这个函数采用两个参数：物品数组和背包容量。函数返回的是最大价值。


int knapsack(Item items[], int capacity)
{
  // 计算物品集合的大小
  int n = sizeof(items) / sizeof(items[0]);
  // 声明一个二维数组，用于存储最大价值
  int value[n + 1][capacity + 1];
  // 初始化第一行和第一列为0
  for (int i = 0; i <= n; ++i)
  {
    value[i][0] = 0;
  }
  for (int w = 1; w <= capacity; ++w)
  {
    value[0][w] = 0;
  }
  // 填充剩余的部分
  for (int i = 1; i <= n; ++i)
  {
    for (int w = 1; w <= capacity; ++w)
    {
      if (items[i - 1].weight <= w)
      {
        value[i][w] = max(value[i - 1][w], value[i - 1][w - items[i - 1].weight] + items[i - 1].value);
      }
      else
      {
        value[i][w] = value[i - 1][w];
      }
    }
  }
  // 返回最大价值
  return value[n][capacity];
}

在这个函数中，我们首先计算物品集合的大小，并定义一个二维数组，用于存储最大价值。我们接着初始化第一行和第一列为0，并用一个嵌套的循环来计算剩余的部分。在这个循环中，我们首先判断如果当前物品的重量小于背包的容量，则可以将它加入背包中，计算在不考虑当前物品时，背包容量为$w$的最大价值和在考虑当前物品时，背包容量为$w-w_i$的最大价值加上当前物品的价值，取其中的较大值保存在$value[i][w]$中。如果当前物品的重量大于背包容量，则不能将其加入背包中，直接将value[i][w]赋值为value[i-1][w]。最后返回value[n][capacity]，即最大价值。

3. 测试

最后，我们可以定义一个简单的测试函数，用于创建一个物品数组，调用$knapsack$函数，并输出结果。


void test_knapsack()
{
  Item items[] = {1, 3, 5, 7};
  int capacity = 7;
  int max_value = knapsack(items, capacity);
  cout << "Max value: " << max_value << endl;
}

在这个测试函数中，我们定义了一个包含四个物品的数组，以及一个容量为7的背包。我们调用$knapsack$函数来计算最大价值，并输出结果。

完整代码如下：


#include <iostream>
using namespace std;
struct Item
  int weight;
  int value;
;
int knapsack(Item items[], int capacity)
{
  int n = sizeof(items) / sizeof(items[0]);
  int value[n + 1][capacity + 1];
  for (int i = 0; i <= n; ++i)
  {
    value[i][0] = 0;
  }
  for (int w = 1; w <= capacity; ++w)
  {
    value[0][w] = 0;
  }
  for (int i = 1; i <= n; ++i)
  {
    for (int w = 1; w <= capacity; ++w)
    {
      if (items[i - 1].weight <= w)
      {
        value[i][w] = max(value[i - 1][w], value[i - 1][w - items[i - 1].weight] + items[i - 1].value);
      }
      else
      {
        value[i][w] = value[i - 1][w];
      }
    }
  }
  return value[n][capacity];
}
void test_knapsack()
{
  Item items[] = {1, 4, 5, 5};
  int capacity = 7;
  int max_value = knapsack(items, capacity);
  cout << "Max value: " << max_value << endl;
}
int main()
{
  test_knapsack();
  return 0;
}

以上就是使用C++实现01背包问题的简单例子。这个算法可以应用于各种实际场景，如货车装载问题、背包旅行问题、网络流最大流问题等。希望这篇文章能够帮助你理解和运用01背包问题的算法。

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

下一篇: 如何在C++中不使用endl语句？

评论区

()

相似文章