【算法】妙不可言---贪心算法

#14天阅读挑战赛#

14天阅读挑战赛

CSDN近期举办14天阅读打卡活动

上篇博客为【算法】妙不可言---算法复杂性_水w的博客-CSDN博客

 

目录

一、上篇小结

二、贪心算法

2.1 贪心选择

2.2 最优子结构

2.3 最优装载问题

三、最优装载问题的代码实现

【时间复杂度&&优化】

【算法精髓】

【最优量度标准】

【源代码】       

---

我们学习了那些经典的算法，在惊叹它们奇妙的同时，难免疑虑重重：这些算法是怎么被想到的？这可能是最费解的地方。

算法作为一门学问，有两条几乎平行的线素。

• 一条是数据结构（数据对象）：数、矩阵、集合、串、排列、图、表达式、分布等。
• 另一条是算法策略：贪心策略、分治策略、动态规划策略、线性规划策略、搜索策略等。

这两条线索是相互独立的：

• 对于同一个数据对象上不同的问题（如单源最短路径和多源最短路径），就会用到不同的算法策略（如贪心策略和动态规划策略）；
• 而对于完全不同的数据对象上的问题（如排序和整数乘法），也许就会用到相同的算法策略（如分治策略）。

两条线索交织在一起，该如何表述呢？

我们早已习惯在一章中完全讲排序，而在另一章中完全讲图论。传统的算法书大多注重内容的收录，却忽视思维过程的展示，因此我们虽然学习了经典的算法，却费解于算法设计的过程。

《趣学算法》本书从问题出发，根据实际问题分析、设计合适的算法策略，然后在数据结构上操作实现，巧妙地将数据结构和算法策略拧成一条线。

全书通过大量实例，充分展现算法设计的思维过程，让读者充分体会求解问题的思路、如何分析、使用什么算法策略、采用什么数据结构、算法的复杂性如何、是否有优化的可能等等。

一、上篇小结

上文主要说了以下问题，

 

二、贪心算法

贪心算法正是活在当下，看清楚眼前”的办法。贪心算法从问题的初始解开始，一步一步地做出当前最好的选择，逐步逼近问题的目标，从而尽可能地得到最优解，即使达不到最优解，也可以得到最优解的近似解。
贪心算法在解决问题的策略上目光短浅。贪心算法只根据当前信息做出选择，而且一旦做出选择，则不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体上做最优考虑，它所做出的选择只是某种意义上的局部最优。在实际应用中，很多问题都可以通过贪心算法得到最优解或最优解的近似解。

贪心算法，“贪心”二字顾名思义，因此其规律特征就是更加注重当前的状态，贪心法做出的选择是对于当前所处状态的最优选择，它的解决问题的视角是微观的“局部”，而不是从全局宏观的角度思考和看待问题，根据这样的性质，要求贪心法解决的问题有“无后效性”——当前的决策不会影响到后续的决策，因为如果问题前后勾连紧密的话，会造成求解过程十分混乱。贪心算法常常用于组合优化问题，它的求解过程是多步判断的过程。

如果一个待求解的问题具有以上的特征，很有可能可以使用贪心算法解决。

对于贪心算法，需要注意以下几个问题。

• 一旦做出选择，就不可以回溯。
• 有可能得不到最优解，而是得到最优解的近似解。
• 选择什么样的贪心策略直接决定算法的好坏。

那么，贪心算法需要遵循什么样的原则呢？

“君子爱财，取之有道”，在贪心算法中，“贪办有道。在遇到具体问题时，有人往往分不清哪些问题能用贪心算法，哪些问题不能用贪心算法。人们经过实践发现，利用贪心算法求解的问题往往具有两个重要的性质：贪心选择和最优子结构。只要满足这两个性质，就可以使用贪心算法。

2.1 贪心选择

贪心选择是指原问题的整体最优解可以通过一系列局部最优的选择得到：先做出当前最优的选择，将原问题变为一个相似却规横更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于末做出的选择。

2.2 最优子结构

最优子结构是指原问题的最优解包含子问题的最优解。

贪心算法通过一系列的局部最优解（子问题的最优解）得到全局最优解（原问题的最优解），如果原问题的最优解和子问题的最优解没有关系，则求解子问题没有任何意义，无法采用贪心算法。例如，对于原问题 S ={ a,a2, a3,....an )，可以在通过贪心选择得到一个当前最优解｛a}之后，转换为求解子问题 S -{ a }，继续求解该子问题，最后对所有子问题的最优解进行合并，即可得到原问题的最优解，如下图所示。

2.3 最优装载问题

装载问题：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。

装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这艘轮船。如果有，找出一种装载方案。最优装载问题要去确定在装载体积不受限制的情况下，将极可能多的集装箱装上轮船。

在载重有限的情况下，有限把重量小的放进去，装的就越多。我们可以采用重量最小优先的贪心策略，从局部最优达到全局最优，从而得到最优装载问题的最优解。

问题描述为：

                  max∑Xi，∑WiXi<=C，Xi∈{0,1}   1<=i<=n

其中，变量Xi=0表示不装入集装箱i，Xi=1表示装入集装箱i。

贪心选择性质：

    设集装箱已依其重量从小到大排序，(X1,X2,…,Xn)是最优装问题的一个最优解。又设k=min{i|Xi=1}。易知，如果给定的最优装载问题有解，则1

    ∑WiYi = Wi - Wk + ∑WiXi <= ∑WiXi <= C

因此，(Yz,Y2,…,Yn)是所给最优装载问题的可行解。

    另一方面，由∑Yi = ∑Xi知，(Y1,Y2,…,Yn)是满足贪心选择性质的最优解。

最优子结构性质：

    设(X1,X2,…,Xn)是最优装载问题的满足贪心选择性质的最优解，则容易知道，X1=1，且（X2,…,Xn）是轮船载重量为C-W1,待装载集装箱为{2,3,…,n}时相应最优集装箱问题的最优解。也及时说，最优集装箱装载问题具有最优子结构性质。

时间复杂度分析：

贪心策略是重量最小的古董先装，每次从余下的古董中选择一个重量最小的古董。

如果采用顺序查找法寻找最小值，则 n 个元素最多需要比较 n 次。第1次选择时有 n 个古董，需要比较 n 次：第2次选择时有 n -1个古重，需要比较 n -1次：...，弟 n 次选举时需要化较1次，总共需要比较 n(n +1)/2次时间复杂度为 O (n^2).

如果采用快速排序法寻找最小值，也就是先从小到大排序，再按顺序选择，则时间复杂度为O(nlogn)，相比顺序査找法更优。

在序列没有变化（静态）的情况下，如果需要多次从序列中选择最小值或最大值，那么可以采用先排序的办法，这样效果更好。

• 把 n 个古董的重量从小到大（非递减）排序。
• 根据贪心策略选择装入的古董，直到不能継续装为止，此时达到最优。

三、最优装载问题的代码实现

【时间复杂度&&优化】

该算法只用一层循环，时间复杂度是O(n);

【算法精髓】

解决最优装载问题之前，需要把所有物体按重量从小到大排序；

该算法使用了include 里自带的 sort(w, w + n)函数，每次向轮船里放物品也按照按物体重量从小到大的顺序向里面放。

Loading(float c, float w, int x){
    创建集装箱数组，存放每个集装箱重量及其序号；
    按集装箱重量从小到大排序；
    有小到大依次判断是否可入箱；
    若当前要放物品的重量小于当前轮船的剩余容量，则可放进去，同时打印输出该物品的重量值；
    返回轮船上箱子总重量；
}

【最优量度标准】

若当前要放物品的重量小于当前轮船的剩余容量，则可放进去，同时打印输出该物品的重量值。

【源代码】       

#include 
#include 
#include 
using namespace std;
 
// 贪心法
// 最优装载问题
void optionalLoad(int w[], int n, int C) {
    sort(w, w + n);//把所有物体按重量从小到大排序
    int retain = C;//retain记录当前剩余容量
    for(int i = 0; i < n; i++) {
        if(w[i] <= retain) {
            cout << w[i] << " ";
            retain -= w[i];
        }
    }
    cout << endl;
}
 
int main() {
    while(true) {
        // n个物体
        int n;
        int x[n+1];
        cout << "请输入物体总数(0退出)：";
        cin >> n;
        if(!n) {
            break;
        }
        int C;//轮船的载重
        cout << "请输入不超过的总重量：";
        cin >> C;
        int w[n];//各个物品的重量
        cout << "分别输入" << n << "个物体的重量：";
        for(int i = 0; i < n; i++) {
            cin >> w[i];
        }
 
        cout << "最优装载为：" << endl;
        optionalLoad(w, n, C);
 
        cout<<"贪心选择结果为:"<
        for(int i=0; i<=n; i++)
        {
            cout<" ";
        }
        cout<
    }
    return 0;
}

运行结果：