算法学习 【第二周】贪心算法实例 Ⅰ

一、前言

在前面一期博客中我们初步了解到了有关贪心算法的基础概念，知道了何为贪心，如何创建贪心算法，本期我们将通过具体的例子来更加深入的了解贪心算法。

好啦，废话不多说，我们开始今天的学习！

二、最优装载问题

海盗们截获一艘装满各种各样古董的货船，每一件古董都价值连城，但一旦打碎就会失去其原有的价值。海盗船虽然足够大，但载重量是有限的。海盗船的载重量为W，每件古董的重量为w_i，如何才能把尽可能多的古董装上海盗船呢?

1、问题分析

上述问题要求我们装载的古董尽可能多，在载重量有限的情况下，优先把重量小的古董装进去，装的古董最多。可以采用重量最小者先装的贪心策略，从局部最优达到全局最优，从而得到最优装载问题的最优解。

问题抽象成数学公式可以这样描述：

2、算法设计

按照贪心算法来说每次选择重量最小的古董先装，依次这样选择直到无法再装下。

如果我们采用顺序查找法寻找最小值，那么如果有n个古董最多需要比较n次，第一次选择有n个古董需要比较n次，第二次选择有n-1个古董，需要比较n-1次依次内推，时间复杂度为O(n²)，这是指数阶算法，不推荐使用。

如果我们采用快速排序法寻找最小值，也就是先从小到大排序，再按照顺序去选择，这样的时间复杂度是O(nlogn)，这是一个对数阶的算法，相比于之前的更加优秀。

3、算法解析

假设，海盗船的载重量W是30，每个古董的重量如下表所示：

我们首先进行第一步，将古董按照重量从小到大进行排序：

最后我们按照顺序去依次选择重量最小的古董装入海盗船（tmp代表已装入的古董重量，ans代表已装入的古董数量）：

可以看到能装入海盗船的古董最多5个。

4、算法详解

我们用一维数组存储古董的重量：

doublew[N];

然后对古董的重量进行排序，这里我们需要用到C++中的排序函数sort，对古董的重量从小到大进行排序：

#include<algorithm>sort(w,w+n);

最后按照贪心策略找出最优解，根据我们上面的演示表我们可以写出如下代码：

intsolve1(intn){
doubletmp=0.0;     //tmp为已装入海盗船的古董重量intans=0;          //ans为装入海盗船的古董数量，初始值为0for(inti=0;i<n;i++){
tmp+=w[i]
if(tmp<=W)
ans++;
elsebreak;
    }
returnans;
}

上述代码我们首先使用变量ans记录装入海盗船的古董数量，并使用变量tmp暂存装入海盗船的古董重量。然后依次检查每个古董，对tmp加上该古董的重量，如果小于或等于载重量W，则令ans++，否则退出。

5、算法分析

• 时间复杂度：我们排序用的sort函数的平均时间复杂度是O(nlogn)，贪心策略的求解的时间复杂度是O(n)，而O(n)\leO(nlogn)，所以总时间复杂度就是O(nlogn)。
  
• 空间复杂度：我们只用了几个辅助空间变量，它们都是常数阶的，所以空间复杂度是O(1)。
  

6、整体代码

以下代码是随书附带的源码，大家可以看一看：

// 最优装载问题 #include<iostream>#include<algorithm> constintN=10005;
usingnamespacestd;
doublew[N];            //古董的重量数组intsolve1(intn,doubleW){
doubletmp=0.0;         //tmp为已装载到船上的古董重量intans=0;          //ans为已装载的古董个数，初始化为0for(inti=0;i<n;i++){
tmp+=w[i];
if(tmp<=W)
ans++;
elsebreak;
    }
returnans;
} 
intsolve2(intn,doubleW){         //优化算法 doubletmp=0.0;         //tmp为已装载到船上的古董重量intans=n;          //ans为已装载的古董个数，初始化为nfor(inti=0;i<n;i++){
tmp+=w[i];
if(tmp>=W){         //最后一次才满足条件 if(tmp==W)
ans=i+1;
elseans=i;
break;
        }     
    }
returnans;
}
intmain(){
intt,n;            //t为测试用例个数，n为古董数量doubleW;           //重量约束 cin>>t;
while(t--){
cin>>W>>n;
for(inti=0;i<n;i++)            //输入每个物品重量cin>>w[i]; 
sort(w,w+n);            //按古董重量升序排序cout<<solve1(n,W)<<endl;
    }
return0;
}

三、最后我想说

本期博客就到这里了，有关贪心算法的实例我会专门分成几个博客来写的，下一期博客就来写有关背包问题的内容。

谢谢大家！