贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
解题的一般步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解。

AM1ng’s Algorithm Blog！

实验题目： 程序存储问题

设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案， 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。
input:第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。
output:输出最多可以存储的程序数。

算法描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int main()
{
    int n,l;
    int count =0;  //计数器计算存储了几个
    cin>>n>>l;
    
    int a[n+1];
    for(int i = 0;i<n;i++)
    { 
        cin>>a[i];
    }
    
    sort(a,a+n);//默认升序
    
    for(int i = 0;i<n;i++)
    {
        if(a[i]<=l)
        {
            l -=a[i];//l 代表总长
            count++;
         }
    }
    
    cout<<count;
    
    return 0;
}

思路描述

1.贪心算法（贪心策略）

目的是要存储最多的程序，贪心算法策略为利用sort函数对程序占用量进行排序，选择最小的，从最小的开始存储，验证得到最优方案里面一定也包含从最小开始选的方案，
说明此策略符合最优解，贪心算法成立。

2.算法解释

利用总长为l，利用数组存储每一个程序占用大小，每存储一个程序，总长l减去对应存储进去程序所需占用的大小，
此时计数器count加一，每次循环更新剩余的l的长度，判断是否够存储下一个程序。

3 复杂度分析
时间复杂度：利用了sort函数对占用大小进行排序，其原理是依据快排，时间复杂度O（n²）

空间复杂度：一维数组O（n）

贪心算法的个人体会和思考

贪心算法总是作出在当前看来最好的选择。
所以难想到利用初步的排序或者按照一定自己来定义的方法进行择优处理，从而达到选取最好的过程。
贪心算法常用于解决最大值或最小值的优化问题。贪心算法能求得最优解的问题一般具有两个重要性质：
贪心选择性质：问题的整体最优解可以通过一系列局部最优的选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法问题和动态规划问题的主要区别。贪心算法通常自顶向下，以迭代的方式做出相继的贪心选择。
最优子结构性质：问题的整体最优解包含子问题的最优解。
贪心算法的基本要素：

1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2.当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

More info: 贪心算法

See U next time！