贪心算法

Weekend for relax ? NEMU : Algorithm.

贪心算法的思想及要点

  贪心算法正如其名,在解决问题时每次都会选择当前情况下的最优解,是一种逼近最优解的算法。他也是一种寻找最优解的方法,即在使用时要把整个问题分解为若干步,在每一步中都会选择当前最优的解法,然后将每一步的解合并成为整个问题的最终解。

  他的问题在于:因为他的贪婪的短视导致在很多情况下都会错过最优解,因为他不会从整体上对问题进行思考,只会闷头于当前情况。所以贪心算法不能用来求最大最小值、无法保证最后的解是最优的、只能求某些特定的解。

  所以实际上可以用贪心算法求得最优解的情况很少,所以我们要证明每一步所作的贪心选择最终能导出问题最优解(举几组数据即可)。

  听起来贪心算法似乎很复杂,但他其实并没有太多的技巧。唯一的考验就在于制定你的贪心策略(主要是要有这个思想) 让你的算法 真正的只关心当下,不去关心后续情况或者先前情况

优化问题的一般描述

优化问题的描述:

1.问题的解为一复杂结构 (x1,x2,…,xn) xi∈Si(可选的方式)

2.约束条件:B(x1,x2…,xn),使B为true的元组称为可行解

3.目标函数f(x1,…,xn)

优化解即指使目标函数取得最值的可行解,对应的目标函数值称为优化值

贪心算法是求近似解的一种主要途径。

例题

下面我们来看一个很简单的例题

例 Loading Problem

设有n个集装箱,集装箱大小一样,第i个设有n个集装箱,集装箱大小一样,第i个集装箱的重量为wi(1≤i≤n),设船的载重量为c.试设计一装船的方法使得装入的集装箱数目最多

这是一道很基础的贪心算法题目,我们先按照优化问题的格式来描述一下他:

令问题的解为(x1,x2,…,xn)  xi={0,1}//代表第i个箱子是否装载。

问题的约束条件是Σi=1,n wixi<=c; //装载箱子的总重量小于等于C

目标函数为 Σi=1,n xi; //装载的集装箱个数

我们的目标是极大化目标函数。

因为目标函数是所装的集装箱数目,所以按照我们的常规思想,那么一定先装重量轻的集装箱。

所以可以写出代码如下

#include <iostream>
#include <algorithm>

using namespace std;

int n,c;
int weight[100]={0};
int countt=0;
int tem_weight=0;
int main()
{
    cin>>n;
    cin>>c;
    for(int i=0;i<n;i++)
    cin>>weight[i];
    sort(weight,weight+n);
    for(int i=0;i<n;i++)
    {
        if(tem_weight+weight[i]<=c)
        {
            tem_weight+=weight[i];
            countt++;
        }
        else {break;}
    }
    cout<<countt<<endl;
    return 0;
}

这时你可能对这种贪心策略存疑,先装载重量低的箱子一定能得到最优解吗?

下面给出证明

证明:

设问题最优解为(y1,y2,…,yn)

如最优解不含箱子1,将箱子1替换优化解中某一个箱子得到一个新的解

1.替换是必须的:若1还能装入船中,则(y1,y2,…,yn)不是优化的

2.因为1是最轻的,所以替换后的解仍是可行的

3.替换后的解装入的箱子数==优化的箱子数,它仍是优化解

4.替换后新的优化解和贪心解都有箱子1

反复替换得到一个优化解,优化解==贪心解

替换次数是有穷的。

这就确定了我们的贪心解一定是优化解。

针对这个问题也引出一点:贪心解虽然在一种策略下只有一个,但问题的真正最优解可能有多个。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

<<<<<<< Updated upstream ======= >>>>>>> Stashed changes