新手天翼
如题，本人想提前预习
最好能发讲义&自己的见解
100豆豆！
中级天翼
贪心：寻找最优解（大部分要排序）
新手天翼
初级启示者
所谓的“贪心算法”，就是每一次面临选择时，选择最优、最先、最X的一项，反正就是突出一个“最”字。比如有1，4，3，2，让你选两个数，令选出来的数最大，你肯定按照每次选择都选择，剩余数中最大的一个数，第一次选择4，剩下还有1，3，2，这时傻子都会选择3啊，从而得出在1，4，3，2这四个数中，选出的两数和是最大的。此时，你就不知不觉地运用到了贪心算法，以最大选择为贪心。
那么，“贪心算法”真正用到编程中是如何呢？下面用一道2013上半年软件设计师的软考题来说明这个问题。
题目是这样的：
设有M台完全相同的机器运行N个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使得完成所有任务所需要的时间最短。假设任务已经按照其运行的时间从大到小来排序，算法基于最长运行时间作业优先的策略：按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。
这里要求定义的变量如下，所有数组的下标皆从0开始：
设，m是机器数，n是任务数，t[]的长度为n，其中每个元素表示任务的运行时间。s[][]长度为mn，下标从0开始，其中s[i][j]表示机器i运行的任务j的编号。d[]长度为m，其中匀速d[i]表示机器i运行的时间，count[]长度为m，其中元素count[i]表示机器i运行的任务数。max为完成所有任务的时间。min,i,j,k为临时定义变量，无意义。
考虑实例m=3（编号0-2），n=7（编号0-6)，各任务的运行时间为{16,14,6,5,4,3,2}（这里其实就是指t[i]定义为{16,14,6,5,4,3,2}，题目没有说）则求各个机器上的运行任务，从任务开始运行到完成所需要的时间。
这道题目，非常长，看起来非常让人头晕，实际上，根本一点都不难。如果你还学过《操作系统》的话，就更简单的。
意思就是将{16,14,6,5,4,3,2}这些数字扔到3个数组里面，使最终，这3个数组里面的数据之和的最大的一个，最小。你也可以想像倒水到3个杯子，要求你每次倒的水的多少只能从{16,14,6,5,4,3,2}这7个数字选一个，必须倒水倒7次，也就是这7个数字选完，最终尽可能让任一一个杯子都不溢出。
你当然是平均化倒水啊，每次倒水的时候，看哪个杯子水量最小倒哪个啊！
这时，就运用到所谓的“贪心算法”了。
最后求出来的结果是17。顺理成章就得到如下的代码，每一次选择都会有一个求最小值的过程：
#include<stdio.h>
void schedule(int m,int n,int *t){
//初始化
int i,j,k,max=0;
int d[100],s[100][100],count[100];
for(i=0;i<m;i++){
d[i]=0;
for(j=0;j<n;j++){
s[i][j]=-1;//-1代表不执行任何任务，不与第0号任务混淆
}
}
//分配前m个任务
//必然是每个机器先分别接受1个任务
for(i=0;i<m;i++){
s[i][0]=i;
d[i]=d[i]+t[i];
count[i]=1;
}
//之后判断哪个机器任务耗时最少，让其接受任务
//尽可能地并行，平均分配任务
for(i=m;i<n;i++){
int min=d[0];
k=0;
for(j=1;j<m;j++){//确定空闲机器，实质是在求当期任务总时间最少的机器
if(min>d[j]){
min=d[j];
k=j;//机器k空闲
}
}
s[k][count[k]]=i;//在机器k的执行队列添加第i号任务
count[k]=count[k]+1;//机器k的任务数+1
d[k]=d[k]+t[i];//机器k的任务执行时间+t[i]，也就是+第i号任务的耗时
}
for(i=0;i<m;i++){//确定完成所有任务需要的时间，实质是求分配完所有任务之后，耗时最多的机器
if(max<d[i]){
max=d[i];
}
}
printf("完成所有任务需要的时间：%d\n",max);
printf("各个机器执行的耗时一览：\n");
for(i=0;i<m;i++){
printf("%d:",i);
for(j=0;j<n;j++){
if(s[i][j]==-1){
break;
}
printf("%d\t",t[s[i][j]]);
}
printf("\n");
}
}
void main(){//测试用例
int time[7]={16,14,6,5,4,3,2};
schedule(3,7,time);
}
最终运行结果如下：
这里，原题目还要对上述代码进行，除去初始化、打印那两步，算法核心的时间复杂度的分析。这个很好求的，不算初始化、打印那两步，分配前m个任务，一个for循环，终止于i<m，这里复杂度为m，之后判断哪个机器任务耗时最小，两层for循环，外层终结于i<m，里层为i<n，因此为mn，最后确定所有任务需要的时间，一个for循环，终止于i<m，这里复杂度为m，也就是m+mn+m，最高维度，用现在的话来说，就是最高次元为mn，因此mn+2m~mn（此乃高等数学的内容，不会面壁去~），也就是时间复杂度为O(mn)。
然而，实际上，由于贪心算法每一次选择都要找一个最优项，遍历数组的每一项都出现一个排序，不像这里一上来就已知一个排好顺序的数组，因此时间复杂度往往是O(n2)，而要是这题给出的数组没有排好序，估计要去到O(m2n2)了。
~~~~~~~~~~~~~~~~~我是分界线~~~~~~~~~~~~~~~~~~~~~~
望采纳，谢谢！~~
缔造者之神
https://baike.so.com/doc/5722655-5935386.html
这个网址里有非常明确的贪心算法讲解。
修练者
我还没有学
高级天翼
呜呜呜，我也没学到~听起来好像很复杂。
【其实我是过来要豆豆的，嘻嘻~这么多豆，谁不想要呢~赏给我吧~】
新手光能
贪心就是贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择
张易晨在2020-07-22 18:40:32追加了内容
总的来说就是a[i]的最优解
张易晨在2020-07-22 19:00:15追加了内容
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，贪心策略使用的前提是局部最优能导致全局最优。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。（百度）
————————————————————————————————————————————————————————
专业说法
张易晨在2020-07-22 19:01:54追加了内容
https://www.jianshu.com/p/18ba3594c7b2
↑这是我能找到的最简单的了
新手天翼
我学到枚举
高级光能
贪心算法的基本思想
贪心算法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好或最优的解。贪婪法的每次决策都以当前情况为基础并根据某个最优原则进行选择，不从整体上考虑其他各种可能的情况。一般来说，这种贪心原则在各种算法模式中都会体现，这里单独作为一种方法来说明，是因为贪婪法对于特定的问题是非常有效的方法。
贪婪法和动态规划法以及分治法一样，都需要对问题进行分解，定义最优解的子结构，但是与其他方法最大的不同在于，贪婪法每一步选择完局部最优解之后就确定了，不再进行回溯处理，也就是说，每一个步骤的局部最优解确定以后，就不再修改，直到算法结束。因为不进行回溯处理，贪婪法只在很少的情况下可以得到真正的最优解，比如最短路径问题、图的最小生成树问题。在大多数情况下，由于选择策略的“短视”，贪婪法会错过真正的最优解，而得不到问题的真正答案。但是贪婪法简单、高效，省去了为找最优解可能需要的穷举操作，可以得到与最优解比较接近的近似最优解，通常作为其他算法的辅助算法来使用。
贪婪法的基本设计思想有以下三个步骤：
建立对问题精确描述的数学模型，包括定义最优解的模型；
将问题分解为一系列的子问题，同时定义子问题的最优解结构；
应用贪心原则确定每个子问题的局部最优解，并根据最优解的模型，用子问题的局部最优解堆叠出全局最优解。
定义最优解的模型通常和定义子问题的最优结构是同时进行的，最优解的模型一般都体现了最优子问题的分解结构和堆叠方式。对于子问题的分解有多种方式，有的问题可以按照问题的求解过程一步一步进行分解，每一步都在前一步的基础上选择当前最好的解，每做一次选择就将问题简化为一个规模更小的子问题，当最后一步的求解完成后就得到了全局最优解。还有的问题可以将问题分解成相对独立的几个子问题，对每个子问题求解完成后再按照一定的规则（比如某种公式或计算法则）将其组合起来得到全局最优解。
这里说的定义子问题分解和子问题的最优解结构可能有点抽象，我们来看一个具体的经典的例子——找零钱。假如，某国发行的货币有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？这个问题的子问题定义就是从四种币值的硬币中选择一枚，使这个硬币的币值和其他已经选择的硬币的币值总和不超过 41 分钱。子问题的最优解结构就是在之前的步骤已经选择的硬币再加上当前选择的一枚硬币，当然，选择的策略是贪婪策略，即在币值总和不超过 41 的前提下选择币值最大的那种硬币。按照这个策略，第一步会选择 25 分的硬币一枚，第二步会选择 10 分的硬币一枚，第三步会选择 5 分的硬币一枚，第四步会选择 1 分的硬币一枚，总共需要 4 枚硬币。
上面的例子得到的确实是一个最优解，但是很多情况下贪婪法都不能得到最优解。同样以找零钱为例，假如，某国货币发行为 25 分、20 分、5 分和 1 分四种硬币，这时候找 41 分钱的最优策略是 2 枚 20 分的硬币加上 1 枚 1 分硬币，一共 3 枚硬币，但是用贪婪法得到的结果却是 1 枚 25 分硬币、3 枚 5 分硬币和 1 枚 1 分硬币，一共 5 枚硬币。
贪婪法的例子：0-1 背包问题
本节课将介绍一个贪婪法的经典例子——0-1 背包问题：有 N 件物品和一个承重为 C 的背包（也可定义为体积），每件物品的重量是 wi，价值是 pi，求解将哪几件物品装入背包可使这些物品在重量总和不超过 C 的情况下价值总和最大。背包问题（Knapsack Problem）是此类组合优化的 NP 完全问题的统称，如货箱装载问题、货船载物问题等，因问题最初来源于如何选择最合适的物品装在背包中而得名，这个问题隐含了一个条件，每个物品只有一件，也就是限定每件物品只能选择 0 个或 1 个，因此又被称为 0-1 背包问题。
来看一个具体的例子，有一个背包，最多能承载重量为 C=150 的物品，现在有 7 个物品（物品不能分割成任意大小），编号为 1~7，重量分别是 wi=[35、30、60、50、40、10、25]，价值分别是 pi=[10、40、30、50、35、40、30]，现在从这 7 个物品中选择一个或多个装入背包，要求在物品总重量不超过 C 的前提下，所装入的物品总价值最高。这个问题的数学模型非常简单，就是一个承重是 C 的背包和 n 个物品，每个物品都有重量和价值两个属性。但是在对问题分析的过程中，我们发现，每个物品还需要一个状态用于标记该物品的选择状态，以确定该物品是否已经被选进背包了，状态是 1 表示物品已经被装到包里了，后续的选择不要再考虑这个物品了。需要特别说明的是状态值为 2 的情况，这种情况表示用当前策略选择的物品导致总重量超过了背包承重量，在这种情况下，如果放弃这个物品，按照策略从剩下的物品中再选一个，有可能就能满足背包承重的要求。因此，设置了一个状态 2，表示当前选择物品不合适，下次选择也不要再选这个物品了。描述每个物品的数据结构 OBJECT 定义为：
typedefstruct{intweight;intprice;intstatus;//0:未选中；1:已选中；2:已经不可选}OBJECT;
接下来是背包问题的定义，背包问题包括两个属性，一个是可选物品列表，另一个是背包总的承重量，简单定义背包问题数据结构如下：
typedefstruct{std::vector objs;inttotalC;}KNAPSACK_PROBLEM;
确定数学模型之后，接下来就要确定子问题了。根据题意，本题的子问题可以描述为：在背包承重还有 C’ 的情况下，选择一个还没有被选择过，且符合贪婪策略的物品装入背包。每选择一个物品 p[i]，都要调整背包的承重量 C’=C’-p[i].weight，问题的初始状态是 C’=150，且所有物品都可以选择。假如选择了一个重为 35 的物品后，子问题就变成在背包容量 C’ 是 115 的情况下，从剩下 6 件物品中选择一个物品。确定了子问题的描述，算法的整体实现过程就是按照选择物品装入背包的过程，按部就班地一步一步解决子问题，直到背包不能再装入物品或所有物品都已经装入背包时，结束算法。
那么如何选择物品呢？这就是贪婪策略的选择问题。对于本题，常见的贪婪策略有三种：第一种策略是根据物品价值选择，每次都选价值最高的物品，根据这个策略最终选择装入背包的物品编号依次是 4、2、6、5，此时包中物品总重量是 130，总价值是 165。第二种策略是根据物品重量选择，每次都选择重量最轻的物品，根据这个策略最终选择装入背包的物品编号依次是 6、7、2、1、5，此时包中物品总重量是 140，总价值是 155。第三种策略是定义一个价值密度的概念，每次选择都选价值密度最高的物品，物品的价值密度 si 定义为 pi/wi，这 7 件物品的价值密度分别为 si=[0.286、1.333、0.5、1.0、0.875、4.0、1.2]。根据这个策略最终选择装入背包的物品编号依次是 6、2、7、4、1，此时包中物品的总重量是 150，总价值是 170。
GreedyAlgo() 函数是贪婪算法的主体结构，包括子问题的分解和选择策略的选择都在这个函数中。能够明显看出来这个算法使用了迭代法的算法模式，当然，这个算法主体的实现还可以使用递归法，正如函数所展示的那样，它可以作为此类问题的一个通用解决思路：
void GreedyAlgo(KNAPSACK_PROBLEM *problem, SELECT_POLICY spFunc){ int idx; int ntc =0;//spFunc 每次选最符合策略的那个物品，选后再检查while((idx = spFunc(problem->objs, problem->totalC - ntc)) !=-1) {//所选物品是否满足背包承重要求？if((ntc + problem->objs[idx].weight) <= problem->totalC) { problem->objs[idx].status =1; ntc += problem->objs[idx].weight; }else{//不能选这个物品了，做个标记后重新选problem->objs[idx].status =2; } } PrintResult(problem->objs);}
spFunc 参数是选择策略函数的接口，通过替换这个参数，可以实现上文提到的三种贪婪策略，分别得到各种贪婪策略下得到的解。以第一种策略为例，每次总是选择 price 最大的物品，可以这样实现：
intChoosefunc1(std::vector& objs,intc){intindex =-1;//-1表示背包容量已满intmp =0;for(inti =0; i (objs.size()); i++) {if((objs[i].status ==0) && (objs[i].price > mp)) { mp = objs[i].price; index = i; } }returnindex;}
看起来第三种策略取得了最好的结果，和动态规划方法得到的最优结果是一致的，但是实际上，这只是对这组数据的验证结果而已，如果换一组数据，结果可能完全相反。当然，对于一些能够证明贪婪策略得到的就是最优解的问题，应用贪婪法可以高效地求得结果，比如求最小生成树的 Prim 算法和 Kruskal 算法。
在大多数情况下，贪婪法受自身策略模式的限制，通常很难直接求解全局最优解问题，也很难用于多阶段决策问题。贪婪法只能得到比较接近最优解的近似的最优解，但是作为一种启发式辅助方法在很多算法中都得到了广泛的应用，很多常用的算法在解决局部最优决策时，都会应用到贪婪法。比如 Dijkstra 的单源最短路径算法在从 dist 中选择当前最短距离的节点时，就是采用的贪婪法策略。事实上，在任何算法中，只要在某个阶段使用了只考虑局部最优情况的选择策略，都可以理解为使用了贪婪算法。
新手启示者
asdfghjkl
高级光能
贪心算法（又称贪婪算法）是指，在对 问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部 最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心选择
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。
最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题
高级守护
本蒟蒻前来蹭贴学习
