C++贪心算法求解0-1背包问题

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

1. 将物品按照单位重量的价值从大到小排序。
2. 依次将物品放入背包中，如果能放下就放入，直到背包装满为止。

以下是使用C++实现贪心算法求解0-1背包问题的代码：

#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 ans = 0; // 最大价值
    // 依次将物品放入背包中
    for (int i = 0; i < n; i++) {
        if (items[i].weight <= capacity) {
            ans += items[i].value;
            capacity -= items[i].weight;
        } else {
            ans += items[i].unitValue * capacity;
            break;
        }
    }
    return ans;
}

int main() {
    int n = 5;
    int capacity = 10;
    item items[n] = {{2, 6}, {2, 3}, {6, 5}, {5, 4}, {4, 6}};
    for (int i = 0; i < n; i++) {
        items[i].unitValue = items[i].value * 1.0 / items[i].weight;
    }
    int ans = knapsack(items, n, capacity);
    cout << "最大价值：" << ans << endl;
    return 0;
}

以上代码的输出结果为：

最大价值：19

其中，物品的重量和价值分别存储在`item`结构体的`weight`和`value`成员变量中，`unitValue`成员变量表示单位重量的价值。使用`sort()`函数将物品按照单位重量价值从大到小排序，然后依次将物品放入背包中，直到背包装满为止。最后返回背包中物品的总价值即为最大价值。