解决背包问题的贪心算法c++代码

背包问题有多种贪心算法，以下是其中一种可以解决 01 背包问题的贪心算法的 C++ 代码：

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

using namespace std;

struct Item {
    int value;
    int weight;

    Item(int v, int w) : value(v), weight(w) {}
};

bool compare(Item a, Item b) {
    double ratio_a = (double)a.value / a.weight;
    double ratio_b = (double)b.value / b.weight;

    return ratio_a > ratio_b;
}

int knapsack(int capacity, vector<Item>& items) {
    sort(items.begin(), items.end(), compare);

    int current_weight = 0;
    int result = 0;

    for (int i = 0; i < items.size(); i++) {
        if (current_weight + items[i].weight <= capacity) {
            current_weight += items[i].weight;
            result += items[i].value;
        } else {
            int remaining_capacity = capacity - current_weight;
            result += items[i].value * ((double)remaining_capacity / items[i].weight);
            break;
        }
    }

    return result;
}

int main() {
    int capacity = 50;
    vector<Item> items = { {60, 10}, {100, 20}, {120, 30} };

    int max_value = knapsack(capacity, items);

    cout << "Maximum value: " << max_value << endl;

    return 0;
}

该算法的思路是先按照每个物品的价值和重量的比例从大到小排序，然后尽可能地选取价值重量比例最大的物品放入背包，直到背包满了为止。如果还有剩余的容量，就按照比例将剩余容量分配给下一个价值比例次高的物品。