贪心法的基本思想

• 把整个问题分解成多个步骤，在每个步骤都选取当前步骤的的最优方案，直到所有步骤结束；
• 在每一步都不考虑对后续步骤的影响，在后续步骤中也不在后头改变前面的选择

如何判断一个题目能用贪心法？

用贪心法求解问题需要满足以下特征：

• 最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理，也就是说局部最优可以扩展到全局最优。
• 贪心选择性质。问题的整体最优解可以通过一系列的局部最优的选择得到。（是该问题可用动态规划算法和贪心算法的关键特征）

常见问题

最少硬币问题

• 某人带着三种面值的硬币去购物，有1元，2元，5元的，硬币数量不限，他需要支付m元，问怎样支付才能使硬币数量最少？
• 根据常识我们首先应该拿出面值最大的，然后依次拿出面值次大的，跟据这样的思想我们可以得到以下程序：

#include<bits/stdc++.h>
using namespace std;
const int NUM = 3;
const int value[NUM] = {1,2,5};
int main(){int money;cin>>money;int ans[NUM] = {0};for(int i = NUM - 1;i>=0;i--){ans[i] = money/value[i];money -=value[i]*ans[i];}for(int i = NUM - 1;i>=0;i--){cout<<value[i]<<"元的硬币数量："<<ans[i]<<endl;}return 0;
}

但是对于一些特殊的面值，此贪心法是无效的。

活动安排问题（区间调度问题）

• 题目：hdu 2037:今年暑假不AC
• 题意抽象：有很多电视节目，给出他们的起止时间，有的节目时间冲突，问能完整看完的电视节目有多少？
• 题解：对最早结束时间进行贪心，算法步骤如下：

把n个活动按结束时间排序。
选择第一个结束的活动，并删除（或跳过）与他时间相冲突的活动
重复上述两步，每次选择剩下的活动中最早结束的那个活动，并删除与它冲突的活动。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
struct node{int start,end;
}record[MAXN];bool cmp(const node& a,const node& b){return a.end<b.end;}
int main(){int n ; cin>>n;//活动数for(int i = 0;i<n;i++){cin>>record[i].start>>record[i].end;}sort(record,record+n, cmp);int lastend = -1;int count = 0;for(int i = 0;i<n;i++){if(record[i].start>=lastend){count++;lastend = record[i].end;}}cout<<count<<endl;return 0;
}

区间覆盖问题

• 给定一个长度为n的区间，再给出m条线段的左端点（起点）和右端点（终点），问最少用多少条线段可以完全覆盖整个区间？
• 题解：

把每个线段按左端点递增排序。
设已经覆盖的区间是[L,R]在剩下的线段中找到所有左端点值小于等于R且右端点最大的线段，把这个线段加入到已经覆盖的区间中去，并且更新已经覆盖的区间[L,R]的值。
重复上一步直到区间全部覆盖。

最优装载问题

• 题目：hdu 2570“迷瘴”
• 题意抽象：有n种药水，体积都是V,浓度不同，把他们混合起来，得到浓度不大于w%的药水，问怎么混合才能得到最大体积的药水？注意：一种药水要么全用要么全不用。
• 题解：

先对药水的浓度从小到大排序，把浓度不大于w%的药水全部加入，并且计算新的浓度，如果药水的浓度大于w%，计算混合后的总浓度，如果不大于w%就加入，否则结束。

多机调度问题

• 题意：设有n个独立的作业，由m台相同的计算机进行加工。作业i的处理时间为T[i]，每一台计算机都可以加工处理，但不能间断，拆分，要求给出一种作业调度方案，在尽可能短的时间内，有m台计算机加工处理完这n个任务
• 题解： 最长处理时间的作业优先

如果n<=m，需要的时间就是这n个任务中处理时间最长的;
如果n>m,首先按n个作业的处理时间从大到小排序，然后按顺序将n个任务分派给空闲的计算机。

Huffman编码

poj 1521"Entropy"

模拟退火

• 模拟退火算法基于物理原理：一个高温的物体降到常温，温度越高时降温的概率越大（降温更快），温度越低时降温的概率越小（降温更慢）。（模拟退火算法利用这样一种思想进行搜索，即进行多次降温（跌代），直到获得一个可行结）
• 在迭代过程中，随机选择下一个状态有两种可能：1.新状态比原状态更优，那么接受新状态；2.新状态更差，那么以一定的概率接受改状态，不过这个概率应随着时间的推移而逐渐降低。
• 模拟退火算法的主要步骤：

设置初始温度T
温度下降，状态转移。从当前温度按降温系数下降到下一个温度，在新的温度计算当前状态；
如果温度降到设定的温度下界，程序结束
B:局部最优点A：全局最优点
模拟退火算法可以条出B点到达A，因 为，他不仅是往上爬山，而且以一定的概率接受比当前点更低的点，使程序有机会摆脱局最优点到达全局最优点。这个概率会随时间逐渐减小，从而最后可以限制在最优解附近。

• 伪代码

eps = 1e-8;   //终止温度，接近0，用于控制精度
T = 100;      //初始温度应该是高温，以100C为例
delta = 0.98;//降温系数控制退火的快慢，小于1，以0.98为例
g(x);        //状态x时的评价函数，例如物理意义上的能量 
now , next;   //当前状态，和新状态
while(T>eps){//如果温度未降到epsg(next),g(now);//计算能量dE = g(next) - g(now);//能量差if(dE >= 0)//新状态更优，接受新状态now = next;else if(exp(dE/T)>rand())//新状态更差，在一定概率下接受改状态e^(dE/T)now = next;T *= delta;//降温模拟退火的过程
}

使用分治法的题目特征

• 平衡子问题：子问题的规模大致相同，可以把问题划分为k个子问题最好k=2,即分为两个规模相等的子问题。（子问题规模相等的处理效率较高）
• 独立子问题：子问题之间相互独立。这也是区分于动态规划算法的根本特征。

分治法法的解题步骤

• 分解（divide）：把问题分解为独立的子问题；
• 解决（conquer）：递归解决子问题；
• 合并（combine）：把子问题的结果合并成原问题的解；

归并排序

归并排序的主要步骤

• 分解：把初始序列分成长度相等的左右两个序列，然后把每个子序列再分成长度相等的左右两个序列，直到子序列只包含一个数。
• 求解子问题：对子序列排序。
• 合并：归并两个有序的子序列，这是归并排序的主要操作。

归并排序代码

#include<bits/stdc++.h>
using namespace std;
const int MAX = 100005;
typedef long long ll;
ll a[MAX] = {5,4,4,7,4,3,2,1,1},b[MAX];void merge(ll l,ll mid,ll r){ll i = l,j = mid+1,t = 0;while(i<=mid&&j<=r){if(a[i]>a[j]){b[t++] = a[j++];}else b[t++] = a[i++];}while(i<=mid) b[t++] = a[i++];while(j<=r) b[t++] = a[j++];for(i = 0;i<t;i++){a[l+i] = b[i];}
}void mergeSort(ll l,ll r){if(l<r){ll mid = (l+r)/2;mergeSort(l,mid);mergeSort(mid+1,r);merge(l,mid,r);}
}
int main(){mergeSort(0,8);for(int i = 0;i<8;i++){cout<<a[i]<<" ";}}

归并排序的应用-逆序对问题

快速排序

快速排序基本思想

• 先从数列中取出一个元素作为基准数；
• 扫描数列，将比基准数小的元素全部放到它的左边，大于或等于基准数的元素部放到它的右边，得到左右两个区间；
• 在对左右区间重复第二步，直达区间少于两个元素；

void swap(int *x,int *y)
{int itmp=*x;*x=*y;*y=itmp;
}
void quicksort(int *arr,unsigned int len)
{if(len<2) return ;int tmp = arr[0];int left = 0,right = len - 1;while(left<right) {while (arr[right] >= tmp && left < right) right--;swap(&(arr[left]),&(arr[right]));while (arr[left]<tmp&&left<right) left++;swap(&(arr[right]),&(arr[left]));}arr[left] = tmp;quicksort(arr,left);quicksort(arr+right+1,len - right -1);
}