贪心策略入门

电玩女神 2023-07-24 11:44 3阅读 0赞

### 贪心策略入门 ###

*   *  适用场景：
     *  贪心算法
     *  贪心选择
     *  最优子结构
     *  举例（活动安排问题）
     *   *   *  问题
             *  分析：
             *  我的代码：
             *  证明算法的正确性：

## 适用场景： ##

求解最优化问题。一般说来，只要具有最优子结构性质（全局最优解里包含子问题的最优解）而且具有贪心选择性质（整体的最优解可以通过局部的一步一步的最优选择来达到）的问题才能用贪心算法。

## 贪心算法 ##

**贪心算法**（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。  
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。  
贪心算法的**基本思路**是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

## 贪心选择 ##

**贪心选择**是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。  
贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。  
通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

## 最优子结构 ##

当一个问题的最优解包含其子问题的最优解时，称此问题具有**最优子结构**性质。  
问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

## 举例（活动安排问题） ##

#### 问题 ####

假设有n个活动的集合E={a1,a2,...,an}，其每个活动都要求使用同一资源（如某个设备、教室、场地等），而在同一时间内只允许一个活动使用这一资源。
        每个活动都有一个要求使用该资源的起止时间si,fi，且si<fi。如果选择了活动ai，则它在半开的时间区间[si,fi)内占有资源。两个活动ai,aj称为是相容的，当且仅当它们的时间区间[si,fi)和[sj,fj)不相交，即si>=fj 或 sj >=fi。现要求在所给定的活动集中选出最大的相容活动子集。

例如:  
输入：

11  
1 3 8  
2 2 13  
3 1 4  
4 5 7  
5 6 10  
6 8 11  
7 12 14  
8 5 9  
9 3 5  
10 0 6  
11 8 12  
输出：  
3：1-4  
4：5-7  
6：8-11  
7：12-14

#### 分析： ####

要让活动个数最多，而且各个活动相容（时间不交叉）。  
贪心准则：每次选出最早结束的，就可以给后面更大的时间空间。（所以要按照结束时间排序，每次只需判断是否与前一活动相容。）

#### 我的代码： ####

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
    //定义允许的最大活动数
    #define Maxn  100
    
    //定义活动的类型
    typedef  struct act_Node
    {
          int Id;       //活动ID
       int s_Time;   //活动开始时间
       int f_Time;   //活动结束时间
    } ACND;
    
    
    //对活动按贪心准则排序
    void Sort(int n,ACND arr[])
    {
        
        act_Node temp;
        for(int j=0; j<n-1; j++){
        
            for(int k=0; k<n-j-1; k++){
        
                if(arr[k].f_Time > arr[k+1].f_Time){
        
                    temp = arr[k];
                    arr[k] = arr[k+1];
                    arr[k+1] = temp;
                }
            }
        }
    }
    
    //进行贪心选择，得到最大相容的活动集合输出
    void Select(int n,ACND arr[])
    {
        
        int k = arr[0].f_Time;
        cout<<arr[0].Id<<":"<<arr[0].s_Time<<"-"<<arr[0].f_Time<<endl;
        for(int j = 1; j<n; j++){
        
            if(k <= arr[j].s_Time){
        
               cout<<arr[j].Id<<":"<<arr[j].s_Time<<"-"<<arr[j].f_Time<<endl;
                k = arr[j].f_Time;
            }
        }
    
    }
    
    
    int main()
    {
          ACND arr[Maxn];
       int an,i;
       cin>>an;           //读入活动个数
       //读入各个活动的编号和占用资源的起止时间
       for(i=0;i<an;i++)
         cin>>arr[i].Id>>arr[i].s_Time>>arr[i].f_Time;
    
       //对活动按贪心准则进行排序
       Sort(an,arr);
    
       //进行贪心选择，获得最优解并输出
       Select(an,arr);
    
      return 0;
    }

#### 证明算法的正确性： ####

证明具有最优子结构性质：  
E（n个元素）是所给活动的集合，A(假设k个元素)是一个最优解，则他们的首元素a1一定相同。那么证明A-a1也是E-a1的最优解即可。  
反证法：假设A-a1不是E-a1的最优解，那么一定存在更优的C，那么显然C的元素个数（假设是l）应该多于A-a1的元素个数（即l>k-1）。则C+a1的元素个数一定多于A的元素个数，即l+1>k，与上面的A是最优解矛盾，得证。  
证明贪心选择性质：  
第一步：证明最优解中包含a1  
如果第一个安排的是ak(k>1)，则用a1置换ak也是最优解。所以我们完全可以选a1而非ak，因为假设有ak的是正确的，但一定是要和a1有交叉的，这并不影响选a1的方案的正确性与过程更优性。  
第二步类似 最优子结构证明：证明做了贪心选择后，原问题被简化为一个更小的与原问题具有相同形式的子问题。