c++写贪心算法求解免费馅饼问题

免费馅饼问题是一个典型的贪心算法问题。具体思路是：每次选择最优的馅饼，直到不能再选择为止。下面是一份C++代码示例：

#include <iostream>
#include <algorithm>
using namespace std;

struct Cake {
    int weight, value;  // 馅饼的重量和价值
};

bool cmp(Cake a, Cake b) {  // 按照单位重量的价值排序
    return a.value * b.weight > b.value * a.weight;
}

double getMaxValue(Cake cakes[], int n, int m) {
    double maxValue = 0.0;  // 最大价值
    sort(cakes, cakes + n, cmp);  // 按照单位重量的价值排序
    for (int i = 0; i < n; i++) {
        if (cakes[i].weight <= m) {  // 当前馅饼可以全部装进背包
            m -= cakes[i].weight;
            maxValue += cakes[i].value;
        } else {  // 当前馅饼不能全部装进背包
            maxValue += m * (double)cakes[i].value / cakes[i].weight;
            break;  // 贪心结束
        }
    }
    return maxValue;
}

int main() {
    int n, m;  // n为馅饼的数量，m为背包的容量
    cin >> n >> m;
    Cake cakes[n];
    for (int i = 0; i < n; i++) {
        cin >> cakes[i].weight >> cakes[i].value;
    }
    cout << getMaxValue(cakes, n, m) << endl;
    return 0;
}

上述代码中，我们首先定义了一个结构体Cake，包含馅饼的重量和价值。然后，我们定义了一个比较函数cmp，用于按照单位重量的价值排序。接着，我们使用sort函数对所有馅饼进行排序。最后，我们使用一个循环贪心地选择馅饼，直到背包无法再装下为止，计算最大价值并返回。