c++贪心算法—背包问题

以下是C++中贪心算法解决背包问题的代码实现：

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

struct item {
    int weight; // 宝物重量
    int value; // 宝物价值
    double cost; // 宝物性价比
};

bool cmp(item a, item b) {
    return a.cost > b.cost; // 按照性价比进行降序排序
}

double knapsack(item arr[], int n, int m) {
    sort(arr, arr + n, cmp); // 对宝物按照性价比进行排序
    double sum = 0; // 毛驴当前能够运走的最大价值
    for (int i = 0; i < n; i++) {
        if (m >= arr[i].weight) { // 如果当前宝物可以全部装进背包
            sum += arr[i].value; // 更新毛驴当前能够运走的最大价值
            m -= arr[i].weight; // 更新背包剩余容量
        } else { // 如果当前宝物无法全部装进背包
            sum += arr[i].cost * m; // 更新毛驴当前能够运走的最大价值
            break;
        }
    }
    return sum;
}

int main() {
    int n, m;
    cin >> n >> m; // 输入宝物数量和背包容量
    item arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i].value >> arr[i].weight; // 输入每个宝物的价值和重量
        arr[i].cost = (double)arr[i].value / arr[i].weight; // 计算每个宝物的性价比
    }
    cout << "毛驴能够运走的最大价值为：" << knapsack(arr, n, m) << endl; // 输出毛驴能够运走的最大价值
    return 0;
}