贪心溯算法并不从整体最优上加以考虑,所作的选择只是在某种意义上的局部最优选择 –> 希望得到整体最优
活动安排问题
/*
* Params:
* 1. int n -> 活动个数
* 2. T s[] -> Start Time Array
* 3. T f[] -> Finish Time Array
* 4. bool A[] -> 选择的活动
* Return: void
* Remark: 输入的数组按照阶*结束时间*非减排序,排序时间复杂度O(nlogn)
*/
template <class T>
void GreedySelector(int n, T s[], T f[], bool A[])
{
A[1] = true; //先选中第一个活动
int current = 1; // j 表示当前选中的结束时间最晚的活动
for (int i = 2; i <= n; i++) {
if(s[i] > f[current]) { // 判断活动的起始时间是否不早于当前活动
A[i] = true;
current = i;
}
else A[i] = false;
}
}
贪心算法的基本要素
贪心选择性质
贪心选择性质是指,所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)达到
最优子结构性质
当一个问题的最优解包含其最解时,称此问题具有最优子结构性质
若A是关于E的活动安排问题包含活动1的一个最优解,则相容活动集合A’=A-{1}是对$E’={i\in E’:s_i \ge f_i}$的活动安排的一个最优解
贪心算法与动态规划算法的差异
贪心算法和动态规划算法都要求问题具有最优子结构性质,这是两类算法的一个共同点.
对比 0-1背包🎒问题和背包问题
/*
* Params:
* 1. int n -> 物品个数
* 2. float M -> 背包容量
* 3. float v[] -> 物品价值数组
* 4. float w[] -> 物品重量数组
* 5. float [] -> 是否选中物品
* Return: void
* Remark: 开始选择前按照按照物品的单位价值v_i/w_i降序排序
*/
void Knapsack(int n, float M, float v[], float w[], float x[]){
Sort(n,v,w);
int i;
for(i=1;i <= n; i++) x[i] = 0;
float c = M; // c为剩余容量
for( i=1 ; i <= n ; i++) {
if(w[i]>c) break;
x[i] = 1;
c -= w[i];
}
if(i <= n) //如果有物品未装入背包
x[i] = c/w[i];
}
