贪心算法普通背包问题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* items, int n, int capacity) {
    sort(items, items + n, cmp);
    int current_weight = 0;
    double current_value = 0.0;
    for (int i = 0; i < n; ++i) {
        if (current_weight + items[i].weight <= capacity) {
            current_weight += items[i].weight;
            current_value += items[i].value;
        }
        else {
            int remaining_capacity = capacity - current_weight;
            current_value += items[i].ratio * remaining_capacity;
            break;
        }
    }
    return current_value;
}

int main() {
    int n, capacity;
    cout << "请输入物品数量和背包容量：" << endl;
    cin >> n >> capacity;
    goods* items = new goods[n];
    cout << "请输入每个物品的重量和价值：" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> items[i].weight >> items[i].value;
        items[i].ratio = (double)items[i].value / items[i].weight;
    }
    double result = knapsack(items, n, capacity);
    cout << "可以装进背包的最大价值为：" << result << endl;
    delete[] items;
    return 0;
}

在此代码中，我们定义了一个结构体 `goods` 来表示物品，其中包括重量、价值和价值与重量比值三个成员变量。在 `cmp` 函数中，我们按照价值与重量比值从大到小排序。在 `knapsack` 函数中，我们首先对物品数组按照价值与重量比值从大到小排序，然后从大到小依次将物品放入背包中，直到背包装满为止。如果当前物品不能完全放入背包中，则将其部分放入背包中，并相应地计算价值。最后返回背包中的总价值。