如何通过贪心算法实现最优装载问题的高效解决

“好事”发生

开始之前推荐一篇实用的文章：《对象池 GenericObjectPool 配置参数详解》，作者：【huazie】。

https://cloud.tencent.com/developer/article/2470887

了解这些配置参数对于正确设置和管理 GenericObjectPool 至关重要，该文的介绍基于commons-pool2-2.4.3 详细说明一下其相关的配置参数。是一篇非常不错的实战文章。

接下来开始我们的正文。

一、贪心算法

具有贪心选择和最优子结构性质就可以使用贪心算法。

1.1、算法知识点

（1）贪心策略，选择当前看上去最好的一个方案。例如，挑选苹果，如果认为个头最大的是最好的，那每次从苹果堆中拿一个最大的，作为最优解；如果认为最红的苹果最好，那么每次从苹果堆中拿一个最红的，作为最优解。因此，根据求解目标不同，贪心策略也会不同。 （2）局部最优解。根据贪心策略，一步步地得到局部最优解。例如，第一次从苹果堆中选一个最大的苹果放起来，记为a1第二次从剩下的苹果堆中选一个最大的苹果放起来，记为a2以此类推。 （3）全局最优解。把所有的局部最优解合并为原来问题的一个最优解（a1,a2,...）。

有点像冒泡排序？是冒泡排序使用了贪心算法，它的贪心策略是每次从剩下的序列中选一个最大的数，然后把这些数放在一起，就得到了从大到小的排序结果。

1.2、算法题目描述

海盗截获了一艘装满各种各样古董的货船，每件古董都价值连城，一旦打碎就失去了它的价值，海盗船载重量为C，每件古董的重量为Wi，海盗们如何尽可能多数量的宝贝装上海盗船？

1.3、做题思路

可以使用贪心算法解出最优装载问题，要求装载的物品数量尽可能多，而船的容量是固定的，那么优先把重量小的物品放进去，使装的物品最多。

采用重量最轻者先装的策略，从局部最优达到全局最优，从而产生最优装载问题的最优解。

（1） 当负载为恒定值c时，Wi越小时，可装载古董的数量就越大。只要选择最小重量的古董，直到无法重新装载。 （2） n个古董的重量从小到大（非递减）排序，然后根据贪婪的策略选择尽可能多的选择前i个古董，直到无法继续安装，此时达到最优。

1.4、算法实现

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

const int N=1000001;

double w[N];//weigths

int main(int argc,char **argv)
{

    double c;
    int n;
    
    cout<<"Please input load and number of antiques:"<<endl;
    cin>>c>>n;
    cout<<"Please enter the weight of each antique, separated by a space:"<<endl;
    
    for(int i=0;i<n;i++)
    {
        cin>>w[i];
    }
    
    sort(w,w+n);
    
    double tmp=0.0;//weight of antique
    int ans=0;//number of antiques
    
    for(int i=0;i<n;i++)
    {
        tmp+=w[i];
        if(tmp<=c)
            ans++;
        else
            break;
    }
    
    cout<<"number of antiques:"<< ans <<endl;
    
    return 0;
}

输出：

Please input load and number of antiques:
30 8
Please enter the weight of each antique, separated by a space:
4 10 7 11 3 5 14 2
number of antiques:5

1.5、算法复杂度分析

（1）时间复杂度：调用sort函数，其平均复杂度为O(n*log n)，贪心策略的for语句时间复杂度为O(n)。因此，时间复杂度为O(n+n*log n)。 （2）空间复杂度：辅组空间是常数阶的，因此为O(1)。

二、总结

贪心算法解决最优装载问题（也称为背包问题，但通常指0/1背包问题的近似解法）的核心思想是：每次都选择单位重量价值最高的物品装载，直到背包装满为止。它并非总是能得到最优解，但通常能得到一个比较好的近似解，尤其在物品数量较多且重量差异不大的情况下效果更好。

• 优点: 算法简单，易于实现，时间复杂度较低 (O(n log n)，主要耗时在排序上)。
• 缺点: 不能保证得到最优解。对于某些物品组合，贪心策略可能导致遗漏一些高价值物品，从而得到次优解。 它更适合作为近似算法，用于快速得到一个较好的解，而不是追求绝对的最优解。 如果需要最优解，则需要使用动态规划等更复杂的算法。