第四章-贪心算法

组合问题中的贪心法：

0-1背包问题：

背包问题（按照价值密度贪心准则，可以达到最优解）：

活动安排问题：

在一个会场中，安排一批活动，活动的时间可能重复，要求计算出最多能够安排的活动数。

输入：第一行为活动数n。后面则有n行，每一行为活动开始时间和结束时间。

输出：最大活动安排数。

算法分析：

先把活动按照时间从大到小的顺序，进行排序。然后就可以用贪心思想来进行选择。

代码：

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

typedef struct node
{
    int start, end;
}node;

int n;
vector<node> v;

bool Compare(node n1, node n2)
{
    return n1.end < n2.end;
}

void Setup()
{
    cin >> n;
    node t;
    for (int i = 0; i < n; i++)
    {
        cin >> t.start >> t.end;
        v.push_back(t);
    }
    sort(v.begin(), v.end(), Compare);
}

int Select()
{
    int maxCount = 1;
    int currectAct = 0;
    for (int i = 1; i < n - 1; i++)        //直接从第二个开始
    {
        if (v[i].start >= v[currectAct].end)
        {
            maxCount++;
            currectAct = i;        //在当前基础上，继续找下一个
        }
    }
    return maxCount;
}

int main()
{
    Setup();
    cout << Select() << endl;
    return 0;
}
/*测试数据：
输入：
5
1 23
12 28
25 35
27 80
36 50
输出：
3
*/

图问题中的贪心法：

其他问题：

汽车加油问题：

汽车加满油之后，能够行驶n公里。沿途有k个加油站。

输入：第一行为n和k。第二行有k+1个数，是加油站之间的距离，第0个和最后一个加油站是起点和终点。

输出：最少加油次数。如果无法到达终点，则输出"No Solution"(如果汽车到达下一个加油站的距离大于n，那么汽车将会在到达加油站之前将油耗尽)。

代码：

#include <iostream>
using namespace std;

int n, k;
int *station;

void Setup()
{
    cin >> n >> k;
    station = new int[k + 1];
    for (int i = 0; i <= k; i++)
    {
        cin >> station[i];
    }
}

int greedy()
{
    int count = 0;
    for (int i = 0; i <= k; i++)
    {
        if (station[i] > n)
        {
            cout << "No Solution" << endl;
            return -1;
        }
    }
    int s = 0;
    for (int i = 0; i <= k; i++)
    {
        s += station[i];    //s代表一次性能走多远的距离
        if (s > n)
        {
            count++;
            //如果加了这一次，而走不下去，那么需要加一次油；另一方面，由于这里的程序是，走过一个加油站而不需要加油的，
            //所以直接重置为到这一个加油站的距离，再加上下一次的距离判断能否继续前进
            s = station[i];
        }
    }
    return count;
}

int main()
{
    Setup();
    cout << greedy() << endl;
}
/*测试数据：
输入：
7 7
1 2 3 4 5 1 6 6
输出：
4
*/

删数问题：

给定两个正整数Number和Count，按照数字Number原来的顺序，删除Count个任意数字后，得到一个新的正整数。请求出得到的最小数字。

输入：按顺序输入Number和Count。

输出：输出最小数字。

代码：

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

unsigned int Count = 0;
string sourceNumber;

void Setup()
{
    cin >> sourceNumber >> Count;
    if (Count > sourceNumber.length())
    {
        cout << "输入无效" << endl;
    }
}

string Greedy()
{
    unsigned int deleteCount = 0, i = 0, accNum = 0;
    while (deleteCount < Count)
    {
        if (sourceNumber[accNum] < sourceNumber[accNum + 1])    //处于递增情况
        {
            accNum++;
            if (accNum == sourceNumber.length() - 1)    //如果一直递增
            {
                sourceNumber.substr(0, Count - 1);
            }
        }
        else    //出现递减的情况
        {
            sourceNumber.erase(accNum, 1);
            accNum = 0;
            deleteCount++;
        }
    }
    return sourceNumber;
}

int main()
{
    Setup();
    cout << Greedy() << endl;
    return 0;
}
/*测试数据：
输入：
123456
4
输出：
12
*/

/*测试数据：
输入：
178543
4
输出：
13
*/

数列极差问题：

给定一个数列，每次擦去任意两个数a、b，然后再向数列中加入一个数a*b+1，重复上述操作，直到数列只剩一个数。从这些数中，选出最大和最小的数：Max、Min，则将数列极差定义为M=Max-Min。

算法分析：

例如一个只有三个数的数列{a，b，c}，假设a<b<c，则可证明上述操作得到的Max=(a*b+1)*c+1，Min=(b*c+1)*a+1。所以对于一般数列来说，

求Max一定要重复地从最小的两个数来操作。而Min相反，要重复地从最大的两个数来操作。一定要记住两次操作要分开完成，不能互相干扰，否则不能得到结果。计算过程如下：

输入：第一行为数列长度，第二行为数列的值。

输出：第一行为M的位数，第二行为M的值。

代码：

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

int n;
vector<int> X, XForMin;

void Setup()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        X.push_back(temp);
        XForMin.push_back(temp);
    }
}

bool CompareForMin(int n1, int n2)
{
    return n1 > n2;
}

int GreedyForMax()
{
    while (X.size() != 1)
    {
        sort(X.begin(), X.end());
        int a = X[0], b = X[1];
        X.erase(X.begin(), X.begin() + 2);
        X.push_back(a * b + 1);
    }
    return X[0];
}

int GreedyForMin()
{
    while (XForMin.size() != 1)
    {
        sort(XForMin.begin(), XForMin.end(), CompareForMin);
        int a = XForMin[0], b = XForMin[1];
        XForMin.erase(XForMin.begin(), XForMin.begin() + 2);
        XForMin.push_back(a * b + 1);
    }
    return XForMin[0];
}

int main()
{
    Setup();
    int M = GreedyForMax() - GreedyForMin();
    int bitsM = 0;
    for (int temp = M; temp != 0; bitsM++)
    {
        temp = temp / 10;
    }
    cout << bitsM << endl << M << endl;
    return 0;
}
/*测试数据：
输入：
6
8 6 5 7 9 1
输出：
4
3672
*/

旅行规划问题：

从A地到B地旅行的距离为d0，汽车油箱容量为c，每升油可以行驶e公里。出发点A地的加油站油价为p。旅途中有n个加油站，每个加油站到A地的距离为di，油价为pi。求旅行的最低花费。

输入：第一行为d0、c、e、p以及n，第二行为di、pi。

输出：旅行的最低花费，要求精确到小数点后2位。如果无法抵达终点B地，则输出"No Solution"。

算法分析：

加油方案可以为(x0, x1, ... , xn , xn)，其中x0为A地的加油站，x1-xn为途中的n个加油站，xi={0，1}，0不加，1加。那么目标值为minΣ_i=0ⁿ(pi * xi)。

首先必须要明白一个问题：到哪一站才加油，每一次加油加多少?——直接选择价格最低的贪心准则，对于第i个加油站，查找汽车最大行驶距离内的、油价最低的（不与此站相比）一个站；重复这个过程，直到终点B地。

代码：