贪心算法

贪心算法

贪心算法:指再对问题求解时，总是做出在当前看来是最好的选择，就是指不同全局考虑问题，做到了局部的最优解。

看了上面的定义，我们在实际应用中，也会懵逼，何时可以用贪心算法？
我们可以从主管角度理解为，贪心算法是问题的解可以通过一步步最优解得到的，总之，贪心算法类问题就那么几类，我们通过这几类问题去了解贪心算法吧

1.背包问题

问题：假设我们有一个容量为100kg的包，现在有一下物品，我们要求在有限容量的条件下，让背包的总价值最大。

tx1.jpg

贪心，就是我们要总价值最大，我们不必先考虑全局，我们就尽可能将价值比最大的物品多装入背包，这个思想就是贪心了。
黄豆的性价比 = 1
绿豆的性价比 = 3
红豆的性价比 = 2
黑豆的性价比 = 4
青豆的性价比 = 1.5
那我们肯定先装黑豆，全部装入，背包剩余80kg,接下来装绿豆，全部装入背包剩余50kg,接下来只能装50kg红豆了。
选择方案:
20kg黑豆+30kg绿豆+50kg红豆 总价值 = 270

void back_Pack()
{
    double sumW = 100, sumV = 0;//背包最大容量100kg
    double weight[] = { 100,30,60,20,50 };
    double value[] = { 100,90,120,80,75 };
    int temp[5] = { 0 }, index;//标记当前物品选择与否
    double bi[5] = { 0 }, maxBi;//性价比
    for (int i = 0; i < 5; i++)
    {
        bi[i] = value[i] * 1.0 / weight[i];
    }
    //开始挑选物品
    for (int i = 0; i < 5; i++)
    {
        maxBi = -9999;
        //挑选当前未选的物品性价比最大的
        for (int j = 0; j < 5; j++)
        {
            if (temp[j] == 0 && bi[j] > maxBi)
            {
                maxBi = bi[j];
                index = j;
            }
        }
        //背包容量不足
        if (sumW <= 0)
        {
            break;
        }
        //背包容量足
        temp[index] = 1;
        if (sumW >= weight[index])
        {
            sumW -= weight[index];//全部放入
            sumV += value[index];
        }
        else {
            sumV += bi[index] * sumW;
            sumW = 0;//容量不足，放入一部分
        }
    }
    //输出最大价值
    printf_s("%lf", sumV);
}

2.活动安排问题

问题：假设现在有几个活动，每个活动用区间[a,b]表示，区间表示活动在时间a开始，时间b结束，且在任何时刻只能进行一个活动，即活动1在某个时间段进行时，后面但凡有活动的区间在活动1范围内，这个活动是不可进行的。
比如，活动1[3,6]，活动2[1,4]，活动3[6,7]活动1和活动2是不可以同时进行的,活动1和活动3可以同时进行。
题目问题是，在给的个活动中，求最大可以安排的活动数目。

活动编号	开始时间	结束时间
1	1	3
2	2	5
3	4	8
4	6	10

分析问题：我们如何让活动安排更多?,采用贪心的策略就是我么每次选择一个可以给后面剩余更多时间的安排，所以，将所有活动按开始时间递增排序。
上面表就是按照活动开始时间递增排序的，首先选择活动1，活动2不选，和活动1冲突了，活动3可以选，活动4不可以选，和活动3冲突。
根据贪心法，我们选择活动1和活动3，最大安排个数是2个。

 void plan_Acivity()
{
    struct plan s[11] = { { 2,5 },{ 4,8 },{ 6,10 },{ 1,3 } };
    struct plan temp;
    int sum = 0;
    //按照活动开始时间排序
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4 - i - 1; j++)
        {
            if (s[j].begin > s[j + 1].begin)
            {
                temp = s[j];
                s[j] = s[j + 1];
                s[j + 1] = temp;
            }
        }
    }
    //开始逐个安排活动
    temp = s[0];
    sum++;
    for (int i = 1; i < 4; i++)
    {
        if (s[i].begin > temp.last)//判断次活动是否可以安排
        {
            sum++;
            temp = s[i];
        }

    }
    printf_s("%d", sum);
}

3.最优装载问题

问题：在一艘轮船上，容量最大为w,现在有一批货物，它们重量分别是W(i)，为了不超过轮船最大装载，我们要装尽可能多的货物，如何装载？

物品编号	物品重量
1	5
2	2
3	5
4	4
5	3

这个问题就十分符合我们主观上的贪心策略，我们首先将所有货物按照重量从小到大排序，然后从第一个后取，直到装不下为止。

所以选择编号为 2，5，4货物去装载。

void load()
{
    int weight[5] = { 5,2,6,4,3 }, temp, maxW = 10;
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5 - i - 1; j++)
        {
            if (weight[j] > weight[j + 1])
            {
                temp = weight[j];
                weight[j] = weight[j + 1];
                weight[j + 1] = temp;
            }
        }
    }
    //开始逐个装载
    for (int i = 0; i < 5; i++)
    {
        if (maxW - weight[i] > 0)
        {
            printf_s("%d\n", weight[i]);
            maxW -= weight[i];
        }
    }
}

4.多机调度问题

设有n个独立的作业，由m台独立的机器进行这些作业的处理，每个作业需要处理的时间是不同的，每个作业均可在任何一个机器上进行，多机调度问题要求给出一种方案，使得所有任务在最短时间内在m台机器上完成作业。
假设机器个数为3个任务是7个任务，下表是每个任务执行时间

任务编号	处理时间
1	2
2	14
3	4
4	16
5	6
6	5
7	3

我们的策略上，用贪心思想，我们要最短时间完成所有的任务，那我们先安排最长时间的任务，让最长任务进行的同时，其它任务在同步进行。将任务按照处理时间递减排序。如下表

任务编号	处理时间
4	16
2	14
5	6
6	5
3	4
7	3
1	2

机器1分配任务4，执行时间16，占用时间段[0,16]
机器2分配任务2，执行时间14，占用时间段[0,14]
机器3分配任务5，执行时间6，占用时间段[0,6]
机器3分配任务6，执行时间5，占用时间段[6,11]
机器3分配任务3，执行时间4，占用时间段[11,15]
机器2分配任务7，执行时间3，占用时间段[14,17]
机器3分配任务1，执行时间2，占用时间段[15,17]
所以最短可在17小时内完成。

5.哈夫曼编码问题

这个问题我们已经在大一离散，大二的数据结构，算法，都直到了，我就不写详细过程了，只分析它是贪心思想，每次找出权值最小的两个点合并。。。。

获取完整代码

我分别用C，C++，JAVA三种主流语言编写了完整代码，请大家指导批正，一起学习。

点击查看