简单易懂的C++背包问题贪心算法 |21xrx.com

简单易懂的C++背包问题贪心算法

2023-07-03 05:42:39 深夜i -- --

C++ 背包问题贪心算法简单易懂

背包问题是计算机算法中最基础的问题之一，而贪心算法是解决背包问题的最常用方法之一。贪心算法是一种基于贪心策略的思想，它通过局部最优的选择来达到全局最优的解。

在贪心算法中，背包问题通常被分为两种类型：0/1背包问题和完全背包问题。0/1背包问题是指一件物品只能选择拿或者不拿，而完全背包问题则允许一件物品选择拿多次。

在C++编程中，我们可以通过简单易懂的代码来实现贪心算法解决背包问题。以下是一个简单的0/1背包问题-贪心算法代码：


#include <iostream>
#include <algorithm>
using namespace std;
struct item
  int weight;
  int value;
;
bool cmp(item a, item b) {
  double r1 = (double)a.value / (double)a.weight;
  double r2 = (double)b.value / (double)b.weight;
  return r1 > r2;
}
double fractionalKnapsack(int W, item arr[], int n) {
  sort(arr, arr + n, cmp);
  int curWeight = 0;
  double finalValue = 0.0;
  for (int i = 0; i < n; ++i) {
    if (curWeight + arr[i].weight <= W) {
      curWeight += arr[i].weight;
      finalValue += arr[i].value;
    } else {
      int remain = W - curWeight;
      finalValue += arr[i].value * ((double)remain / (double)arr[i].weight);
      break;
    }
  }
  return finalValue;
}
int main(){
  int W = 50;
  item arr[] = {10, 100, 120};
  int n = sizeof(arr) / sizeof(arr[0]);
  double ans = fractionalKnapsack(W, arr, n);
  cout << "The maximum value we can obtain: " << ans << endl;
  return 0;
}

这段代码实现的是一个0/1背包问题。该问题的描述为：有一组物品，每种物品都有自己的重量和价值，在限定的总重量内，选择其中若干件物品，使得物品的总价值最大。实现代码中，我们通过结构体 `item` 存储了每种物品的重量和价值，并通过 `cmp`函数定义物品选择的优先级。代码中的 `fractionalKnapsack` 函数即为通过贪婪策略来计算能装满背包中物品的最大价值。

选择这篇文章，基于我们的NLP模型认为您是一名Python开发者，因此以上代码中C++的解释是英语而非中文。以上内容仅供参考。

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

下一篇: C++编程：字符串反转（逆序输出）实现

评论区

()

相似文章