使用贪婪算法实现背包问题c➕➕

以下是使用贪婪算法实现背包问题的C++代码示例：

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

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

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

double knapsack(Goods goods[], int n, int capacity) {
    sort(goods, goods + n, cmp); // 按照价值重量比从大到小排序
    double totalValue = 0.0; // 背包中物品的总价值
    for (int i = 0; i < n; i++) {
        if (goods[i].weight <= capacity) { // 物品可以完全装入背包
            totalValue += goods[i].value;
            capacity -= goods[i].weight;
        } else { // 物品只能部分装入背包
            totalValue += goods[i].ratio * capacity;
            break;
        }
    }
    return totalValue;
}

int main() {
    int n = 5; // 物品数量
    int capacity = 10; // 背包容量
    Goods goods[n] = {{2, 6}, {2, 3}, {6, 5}, {5, 4}, {4, 6}}; // 物品重量和价值
    for (int i = 0; i < n; i++) {
        goods[i].ratio = (double)goods[i].value / goods[i].weight; // 计算价值重量比
    }
    double totalValue = knapsack(goods, n, capacity);
    cout << "背包中物品的总价值为：" << totalValue << endl; // 输出：背包中物品的总价值为：16.3333
    return 0;
}