贪心法解决背包问题代码

以下是使用贪心算法解决背包问题的代码，其中物品按照单位重量价值从大到小排序，然后依次将单位重量价值较大的物品放入背包中，直到背包装满或者所有物品都放入背包中。这里使用了一个结构体来存储每个物品的重量、价值和单位重量价值。

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

struct Item {
    int weight;
    int value;
    double unitValue;
};

bool cmp(Item a, Item b) {
    return a.unitValue > b.unitValue;
}

double knapsack(Item items[], int n, int capacity) {
    sort(items, items + n, cmp); // 按照单位重量价值从大到小排序
    double totalValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (items[i].weight <= capacity) { // 如果物品可以全部放入背包
            totalValue += items[i].value;
            capacity -= items[i].weight;
        } else { // 如果物品只能部分放入背包
            totalValue += items[i].unitValue * capacity;
            break;
        }
    }
    return totalValue;
}

int main() {
    int n, capacity;
    cin >> n >> capacity;
    Item items[n];
    for (int i = 0; i < n; i++) {
        cin >> items[i].weight >> items[i].value;
        items[i].unitValue = (double) items[i].value / items[i].weight;
    }
    double totalValue = knapsack(items, n, capacity);
    cout << totalValue << endl;
    return 0;
}