算法学习之贪心法

定义

贪心法是在对问题进行求解时，只做出在当前情况下最好的解，即局部最优解（而动态规划是整体最优解）

解题的一般步骤

建立数学模型，来描述问题把问题分解成若干个子问题对每一子问题求解，得到子问题局部最优解把每一个子问题的局部最优解合并成一个解

例1：活动选择问题

有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。 #include<iostream> #include<algorithm> using namespace std; struct Act { int start; int end; }act[100]; bool cmp(Act a, Act b) { return a.end < b.end; } int main() { cout << "可供安排的的活动总数为:" << endl; int m; cin >> m; cout << "请依次输入安排的活动的起止时间：" << endl; for (int i = 0; i < m; i++) { cin >> act[i].start >> act[i].end; } sort(act, act + m, cmp);//排序函数 cout << "可最多安排的活动为：" << endl; cout << act[0].start <<" "<< act[0].end << endl; int sum = 1;//安排的活动总数 int i = 0; for (int j = 1; j < m; j++) { if (act[j].start >= act[i].end) { i = j; sum++; cout << act[j].start <<" "<< act[j].end << endl; } } cout << "最多安排的活动总数为：" << sum; } 解析：该题可采用贪心法，按活动的最早结束时间来获得局部最优解

例2：纸币找零问题

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元， 至少要用多少张纸币？ #include<iostream> using namespace std; int main() { int count[] = { 4,3,5,1,3,2,1 };//每张面值对应的数量 int value[] = { 1,2,5,10,20,50,100 };//面值 cout << "请输入你需要找零的金额：" << endl; int n; cin >> n; int sum=0;//找零钱币总数 for (int i = 6; i >= 0; i--){ while (n >= value[i]) { n -= value[i]; sum++; } } if (n == 0) { cout << "至少共需要" << sum << "张纸币"; } else { cout << "找不开"; } }

解析：运用贪心法，每一步找面值最大的纸币