贪心算法01背包问题c

下面是使用贪心算法求解01背包问题的C++代码：

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

// 物品结构体
struct Item {
    int value;
    int weight;
    double density; // 单位价值
};

// 贪心算法求解01背包问题
double knapsack(int W, Item items[], int n) {
    // 计算每个物品的单位价值
    for (int i = 0; i < n; i++) {
        items[i].density = (double)items[i].value / items[i].weight;
    }

    // 按照单位价值从大到小排序
    sort(items, items + n, [](Item a, Item b) {
        return a.density > b.density;
    });

    double totalValue = 0.0;
    int remainingWeight = W;

    for (int i = 0; i < n; i++) {
        if (remainingWeight >= items[i].weight) { // 当前物品可以装进背包
            totalValue += items[i].value;
            remainingWeight -= items[i].weight;
        }
        else { // 当前物品无法完全装进背包，只能装一部分
            totalValue += remainingWeight * items[i].density;
            break;
        }
    }

    return totalValue;
}

int main() {
    int W = 50; // 背包容量
    Item items[] = {{60, 10}, {100, 20}, {120, 30}}; // 物品列表
    int n = sizeof(items) / sizeof(items[0]); // 物品数量

    double maxValue = knapsack(W, items, n);

    cout << "The maximum value that can be put into the knapsack is: " << maxValue << endl;

    return 0;
}

代码中，我们首先计算每个物品的单位价值，然后按照单位价值从大到小排序。接着依次考虑每个物品，如果当前物品可以完全装进背包，则将其放入背包并更新剩余容量；否则只能装一部分，将其放入背包，并终止循环。

注意，贪心算法并不保证一定能够得到最优解，但在一些特定情况下，它的解可以非常接近最优解。