部分背包贪心算法c++

部分背包问题是指对于每种物品，我们可以选择拿走一部分，而不是必须全拿或者全不拿。以下是部分背包贪心算法的C++代码：

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

using namespace std;

struct Item {
    int weight;
    int value;
};

bool cmp(Item a, Item b) {
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

double fractionalKnapsack(int W, vector<Item> items) {
    sort(items.begin(), items.end(), cmp);
    int n = items.size();
    double res = 0.0;
    for (int i = 0; i < n; i++) {
        if (W == 0) {
            return res;
        }
        int wt = min(items[i].weight, W);
        res += wt * ((double)items[i].value / items[i].weight);
        W -= wt;
    }
    return res;
}

int main() {
    int W = 50; // 背包容量
    vector<Item> items{ {10, 60}, {20, 100}, {30, 120} };
    double max_value = fractionalKnapsack(W, items);
    cout << "Maximum value we can obtain = " << max_value << endl;
    return 0;
}

其中，`Item`结构体表示物品的重量和价值，`cmp`函数用于比较每个物品的单位价值（即价值除以重量），按照从大到小的顺序排序，`fractionalKnapsack`函数用于求解部分背包问题，返回可以得到的最大价值。