c++贪心算法

C++贪心算法是一种通过每次选择当前最优解的局部最优策略来求解问题的方法。下面是一个用C++实现贪心算法的示例：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 贪心算法求解背包问题
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<pair<double, int>> valuePerWeight(n); // 存储每个物品的单位价值（价值/重量）

    // 计算每个物品的单位价值
    for (int i = 0; i < n; i++) {
        valuePerWeight[i].first = values[i] / (double)weights[i];
        valuePerWeight[i].second = i;
    }

    // 按单位价值降序排序
    sort(valuePerWeight.begin(), valuePerWeight.end(), greater<pair<double, int>>());

    int totalValue = 0; // 总价值
    int currentWeight = 0; // 当前背包容量

    // 选择单位价值最高的物品，直到背包装满或没有物品可选
    for (int i = 0; i < n && currentWeight < capacity; i++) {
        int index = valuePerWeight[i].second;
        if (weights[index] + currentWeight <= capacity) {
            totalValue += values[index];
            currentWeight += weights[index];
        } else {
            int remainingCapacity = capacity - currentWeight;
            totalValue += valuePerWeight[i].first * remainingCapacity;
            currentWeight = capacity;
        }
    }

    return totalValue;
}

int main() {
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int capacity = 8;

    int maxValue = knapsack(weights, values, capacity);
    cout << "最大价值: " << maxValue << endl;

    return 0;
}

以上示例是一个贪心算法用于求解背包问题的实现。其中，knapsack函数接受物品的重量和价值数组，以及背包的容量，返回能够放入背包的物品的最大总价值。主函数中定义了一个背包容量为8的背包，并定义了4个物品的重量和价值数组，然后调用knapsack函数来求解最大总价值，并输出结果。

贪心算法的核心思想在于每次选择当前最优解，然后再基于已选择的最优解继续选择下一个最优解，以此类推，直到无法选择下一个最优解或达到问题的要求。在背包问题中，每次选择单位价值最高的物品放入背包，并计算总价值。