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

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

2023-07-11 18:44:55 深夜i -- --

C++ 背包问题代码

背包问题是计算机科学中的一个经典问题，旨在找到可以放入背包的最大价值的物品组合。C++作为一种广泛使用的编程语言，在解决背包问题方面也可以发挥大展身手。下面是使用C++实现背包问题的代码示例。

首先，我们需要定义如下的背包类：


class Knapsack {
public:
  int weight;
  int value;
  Knapsack(int w, int v):weight(w), value(v){};
};
bool cmp(Knapsack a, Knapsack b)
  return a.value > b.value;

这个类包含了背包的重量和价值两个属性，并且有一个用于比较两个物品价值的函数。接着，我们需要定义一个函数来计算背包最大价值（即针对一组物品，给定背包容量后能获得的最大价值）。下面是这个函数的示例代码：


int knapsack(int capacity, vector<Knapsack>& packs) {
  int size = packs.size();
  sort(packs.begin(), packs.end(), cmp);
  int res = 0;
  for(int i = 0; i < size; i++) {
    if(capacity < packs[i].weight) break;
    res += packs[i].value;
    capacity -= packs[i].weight;
  }
  return res;
}

这个函数首先对物品按照价值排序，然后逐个物品地考虑是否放入背包中。当背包容量不足以放下当前物品时，就跳出循环并返回当前总价值。

最后，我们可以在主函数中使用这个函数来计算给定背包容量下的最大价值，如下所示：


int main() {
  int capacity = 50;
  vector<Knapsack> packs = {
    Knapsack(10, 60),
    Knapsack(20, 100),
    Knapsack(30, 120)
  };
  int res = knapsack(capacity, packs);
  cout << "The maximum value of knapsack is: " << res << endl;
  return 0;
}

以上就是使用C++实现背包问题的示例代码。这个代码可以方便地处理一组给定的物品，找出能够放入背包的最大价值。在实际应用中，我们也可以根据需要修改代码，进行更加高效的计算。

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

下一篇: C++函数编写指南

评论区

()

相似文章