贪心算法之最优装载问题

贪心算法之最优装载问题"/>

贪心算法之最优装载问题

最优装载问题

• 贪心算法
• • 算法知识点
  • 算法题目描述
  • 做题思路
  • 算法实现
  • 算法复杂度分析

14天阅读挑战赛
努力是为了不平庸~。
数据结构+算法=程序。 数据结构是程序的骨架，算法是程序的灵魂。

贪心算法

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

算法知识点

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

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

算法题目描述

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

做题思路

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

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

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

算法实现

#include <iostream>
#include <algorithm>
using namespace std;const int N=1000001;double w[N];//weigthsint 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 antiqueint ans=0;//number of antiquesfor(int i=0;i<n;i++){tmp+=w[i];if(tmp<=c)ans++;elsebreak;}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）时间复杂度：调用sort函数，其平均复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)，贪心策略的for语句时间复杂度为 O ( n ) O(n) O(n)。因此，时间复杂度为 O ( n + n log ⁡ n ) O(n+n\log n) O(n+nlogn)。
（2）空间复杂度：辅组空间是常数阶的，因此为 O ( 1 ) O(1) O(1)。