贪心算法C++常考模板

贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好的策略。在 C++ 中，贪心算法通常用于解决一些可以分解成一系列局部最优解的问题，比如最短路径、背包问题等。

下面是一个简单的贪心算法模板示例，用于求解 Knapsack 问题（0-1背包问题）的最小重量解决方案：

#include <iostream>
#include <vector>

using namespace std;

// 定义物品类，包含价值和重量
struct Item {
    int value;
    int weight;
};

bool compareItems(const Item& item1, const Item& item2) {
    return item1.value / item1.weight > item2.value / item2.weight; // 按价值密度排序
}

int knapSack(vector<Item>& items, int W) {
    sort(items.begin(), items.end(), compareItems); // 贪心选择价值密度大的物品

    int totalValue = 0;
    for (Item& item : items) {
        if (W >= item.weight) { // 如果剩余容量足够，添加该物品
            totalValue += item.value;
            W -= item.weight;
        } else { // 否则，只能携带部分重量
            totalValue += item.value * (W / item.weight);
            break;
        }
    }
    return totalValue;
}

int main() {
    vector<Item> items = {{60, 10}, {100, 20}, {120, 30}}; // 示例物品列表
    int W = 50; // 包容的最大重量
    cout << "最大总价值: " << knapSack(items, W) << endl;
    return 0;
}