c++背包问题贪心算法

背包问题是一个经典的动态规划问题，但是也可以使用贪心算法来解决。以下是使用贪心算法解决 0/1 背包问题的步骤：

1. 计算每个物品的单位价值，即价值与重量的比值。
2. 按照单位价值从大到小的顺序对物品进行排序。
3. 从价值最高的物品开始，依次放入背包中，直到放不下为止。

代码实现如下：

#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;
}

int knapsack(Item items[], int n, int capacity) {
    sort(items, items + n, cmp); //按单位价值从大到小排序
    int curWeight = 0;
    double curValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (curWeight + items[i].weight <= capacity) {
            curWeight += items[i].weight;
            curValue += items[i].value;
        } else {
            int remainWeight = capacity - curWeight;
            curValue += items[i].unitValue * remainWeight;
            break;
        }
    }
    return curValue;
}

int main() {
    Item items[] = {{10, 60}, {20, 100}, {30, 120}};
    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 50;
    for (int i = 0; i < n; i++) {
        items[i].unitValue = items[i].value * 1.0 / items[i].weight;
    }
    cout << "Max value: " << knapsack(items, n, capacity) << endl;
    return 0;
}

以上代码中，Item 结构体表示一个物品，其中 weight 表示重量，value 表示价值，unitValue 表示单位价值。在 knapsack 函数中，首先按照单位价值从大到小排序，然后依次将物品放入背包中，直到放不下为止。如果当前物品无法完全放入背包中，那么就只放入能够放下的部分，然后结束循环。最后返回当前背包的总价值。