基础算法思想

贪心法
- 贪心法的基本思想
- 如何判断一个题目能用贪心法？
- 常见问题
- - 最少硬币问题
  - 活动安排问题（区间调度问题）
  - 区间覆盖问题
  - 最优装载问题
  - 多机调度问题
- Huffman编码
- - [poj 1521"Entropy"](http://poj.org/problem?id=1521)
- 模拟退火
分治法
- 分治法的基本思想
- 使用分治法的题目特征
- 归并排序
- - 逆序对问题
- 快速排序

贪心法贪心法的基本思想

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

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

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

最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理，也就是说局部最优可以扩展到全局最优。
贪心选择性质。问题的整体最优解可以通过一系列的局部最优的选择得到。

常见问题最少硬币问题

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

#include
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< 
但是对于一些特殊的面值，此贪心法是无效的。 
活动安排问题（区间调度问题） 
题目：hdu 2037:今年暑假不AC
题意抽象：有很多电视节目，给出他们的起止时间，有的节目时间冲突，问能完整看完的电视节目有多少？
题解：对最早结束时间进行贪心，算法步骤如下： 
 
 把n个活动按结束时间排序。
 选择第一个结束的活动，并删除（或跳过）与他时间相冲突的活动
 重复上述两步，每次选择剩下的活动中最早结束的那个活动，并删除与它冲突的活动。
  
 
#include
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
    int n ; 
    cin>>n;//活动数
    for(int i = 0;i
        cin>>record[i].start>>record[i].end;
    }
    sort(record,record+n, cmp);
    int lastend = -1;
    int count = 0;
    for(int i = 0;i
         if(record[i].start>=lastend){
             count++;
             lastend = record[i].end;
         }
    }
    cout< 
区间覆盖问题 
给定一个长度为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){//如果温度未降到eps
    g(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;//降温模拟退火的过程
}
 
分治法 
分治法的基本思想 
使用分治法的题目特征 
归并排序 
逆序对问题 
快速排序

基础算法思想

C/C++/C#相关栏目本月热门文章