贪心算法(听课笔记) 所谓贪心算法指的是为了解决在不回溯的前提之下，找出整体最优或者接近最优解的这样一种类型的问题而设计出来的算法。贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。
一、活动安排问题
这个问题指的是一个资源在某个时间点上只能由某个对象独占使用，因此出现了资源争夺的问题。贪心算法在这里主要是解决资源的分配使用问题。贪心算法给出了在一定的时间段上资源给最多个对象使用的一种最优解。
假设有活动集合E={n1,n2,n3...}，并且每个活动的开始时间集合定义为S={s1,s2,s3...}结束时间集合定义为F={f1,f2,f3...}，那么活动i和活动j的进行时间可以用区间[si,fi),[sj,fj)来表示，当si>=fj或者sj>=fi时我们称为两个活动不冲突，也就是说这两个活动可以被安排分别独占使用资源。贪心算法来解决这个问题的思想是首先根据活动的结束时间将所有活动按升序排序，然后首先设定第一个活动选入可以独占使用资源的活动集合，之后依次比较待选集合当中活动是否与选中集合当中最后一个活动冲突，如果不冲突则选入活动。整个思想确保了资源的在使用时间最长，并且将得出最多活动使用资源解集当中的一个解。具体算法如下：
void arrange(int s[],int f[],bool A[],int n)
{ A[0] = true; int lastSelected = 0; for (int i = 1;i < n;i++) if (s[i] >= f[lastSelected]) { A[i] = true; lastSelected = i; } else A[i] = false; } 这里特别需要注意的是，使用这个算法之前必须将所有的活动按照结束时间做升序排列，否则可能得到最差解。
二、背包问题
所谓背包问题指的是一个背包给定能够容纳的最大总量，并且给定一些物品，每个物品有重量和价值两种属性，而物品本身是可以拆分的，也就是说可以放入物品的一个部分，背包问题的目的是放入到背包当中的物品总价值的最大化。这个问题符合贪心算法的两个性质：放入背包的物品可以无限细分，并且单位重量的价值最大化可以导致整体重量的价值最大化。因此，我们可以用贪心算法来解决这个问题。其主要思想如下：算出每个物品的单位重量价值，并根据这个数据将所有物品做降序排列，此后依次选入物品，当选如物品后重重量超出背包所能容纳的最大重量时计算最后一个物品放入的百分比。
|
|
|
