贪心算法 奶牛书架c++

贪心算法是一种在每个阶段选择局部最优解，从而希望最终能够得到全局最优解的算法。奶牛书架问题是一个典型的贪心算法应用问题。下面是一个使用C++实现的奶牛书架问题的贪心算法示例：

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

struct Book {
    int height;
    int width;
};

bool compare(Book a, Book b) {
    return a.height > b.height;
}

int main() {
    int n; // 书的数量
    cin >> n;
    vector<Book> books(n);
    for (int i = 0; i < n; i++) {
        cin >> books[i].height >> books[i].width;
    }
    sort(books.begin(), books.end(), compare); // 按照书的高度降序排序

    int maxHeight = 0; // 当前书架的最大高度
    int totalWidth = 0; // 当前书架的总宽度
    int shelfCount = 0; // 书架的数量

    for (int i = 0; i < n; i++) {
        if (totalWidth + books[i].width <= 100) { // 如果当前书可以放在当前书架上
            totalWidth += books[i].width;
            maxHeight = max(maxHeight, books[i].height);
        } else { // 如果当前书无法放在当前书架上
            shelfCount++;
            totalWidth = books[i].width;
            maxHeight = books[i].height;
        }
    }
    shelfCount++; // 最后一个书架

    cout << shelfCount << " " << maxHeight << endl;

    return 0;
}