请帮忙用c++写一个用贪心算法解决背包问题的代码

好的，这里给你一个使用贪心算法求解 0/1 背包问题的 C++ 代码实现：

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

using namespace std;

struct item {
    int weight;
    int value;
};

bool cmp(item i1, item i2) {
    return i1.value * i2.weight > i2.value * i1.weight;
}

pair<int, vector<int>> knapsack(vector<item>& items, int capacity) {
    int n = items.size();
    vector<int> selected_items(n, 0);
    int total_value = 0;
    sort(items.begin(), items.end(), cmp);
    for (int i = 0; i < n; i++) {
        if (capacity == 0) break;
        if (items[i].weight <= capacity) {
            selected_items[i] = 1;
            total_value += items[i].value;
            capacity -= items[i].weight;
        } else {
            selected_items[i] = capacity / items[i].weight;
            total_value += selected_items[i] * items[i].value;
            capacity -= selected_items[i] * items[i].weight;
        }
    }
    return make_pair(total_value, selected_items);
}

int main() {
    vector<item> items = {{2, 10}, {3, 15}, {5, 20}};
    int capacity = 8;
    auto result = knapsack(items, capacity);
    cout << "Total value: " << result.first << endl;
    cout << "Selected items: ";
    for (int i : result.second) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

这个程序使用了 C++ 中的结构体来表示每个物品的重量和价值，使用了 C++ 11 中的 pair 类型来返回两个值。贪心策略是按照价值重量比从大到小排序，然后依次选择价值重量比最大的物品加入背包中。如果当前物品不能全部装入背包，则选择部分装入。

这个程序的时间复杂度为 $\mathcal{O}(n\log n)$，其中 $n$ 是物品的数量。