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

0-1背包问题是一种经典的NP完全问题，贪心算法无法得到最优解，但可以通过贪心思想得到一种近似最优解的算法。具体实现如下：

1.按照物品的价值重量比从大到小排序；
2.依次将物品放入背包，如果可以放下，则全部放入，否则只放入部分。

下面是C++代码实现：

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

using namespace std;

struct Item {
    int weight; // 物品重量
    int value; // 物品价值
    double v_w; // 价值重量比
};

bool cmp(Item a, Item b) {
    return a.v_w > b.v_w; // 按照价值重量比从大到小排序
}

int knapsack(int W, vector<Item> items) {
    sort(items.begin(), items.end(), cmp);
    int n = items.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (W >= items[i].weight) {
            ans += items[i].value;
            W -= items[i].weight;
        } else {
            ans += W * items[i].v_w;
            break;
        }
    }
    return ans;
}

int main() {
    int W = 50; // 背包容量
    vector<Item> items{{10, 60}, {20, 100}, {30, 120}}; // 物品重量和价值
    for (int i = 0; i < items.size(); i++) {
        items[i].v_w = (double)items[i].value / items[i].weight;
    }
    int ans = knapsack(W, items);
    cout << "最大价值为：" << ans << endl;
    return 0;
}

这里我们构造了三个物品，分别重量为10、20、30，价值为60、100、120，背包容量为50。程序输出结果为最大价值为：240，即将重量为10和20的物品全部放入背包，重量为30的物品只取一部分放入背包。