贪心算法最优装载问题代码c++

贪心算法最优装载问题是指在一艘载重量为C的轮船上，有n个集装箱需要装载，其中第i个集装箱的重量为wi。装载时，必须将集装箱一件件地放入轮船中。对于每个集装箱，可以选择将其装入轮船或不装入轮船，但不能将其切割成小块进行装载。问应如何选择才能使轮船的装载量最大？

贪心算法最优装载问题的解题思路是每次选择当前剩余载重中能放置最重的货物放进去，这样可以尽可能地利用剩余的载重。

以下是使用c++实现贪心算法最优装载问题的代码示例：

#include<iostream>
#include<algorithm>
using namespace std;
struct goods {
    int weight;   //货物重量
    int index;   //货物编号
};
bool cmp(goods a, goods b) {   //按货物重量从大到小排序
    return a.weight > b.weight;
}
int main() {
    int n, c;   //n为货物数量，c为轮船载重量
    cin >> n >> c;
    goods *g = new goods[n];
    for (int i = 0; i < n; i++) {
        cin >> g[i].weight;
        g[i].index = i;
    }
    sort(g, g + n, cmp);   //按货物重量从大到小排序
    int *result = new int[n];
    int sum = 0;   //记录当前已装载货物总重量
    for (int i = 0; i < n; i++) {
        if (sum + g[i].weight <= c) {   //若当前货物可以全部放进去，则全部放进去
            result[g[i].index] = 1;
            sum += g[i].weight;
        }
        else {   //否则只能放部分货物
            result[g[i].index] = (c - sum) / g[i].weight;
            sum += result[g[i].index] * g[i].weight;
        }
    }
    cout << "最大装载量为：" << sum << endl;
    cout << "选择的货物编号为：";
    for (int i = 0; i < n; i++) {
        if (result[i] == 1) {
            cout << i + 1 << " ";
        }
    }
    cout << endl;
    delete[]g;
    delete[]result;
    return 0;
}