贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出当前看来是最好的选择,就能得到问题的答案。
虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解。在一些情况下,即使贪心算法不能得到整体最优解,但其实,最终结果却是最优解的很好的近似解。
贪心算法是一种解决问题的策略,如果策略正确,那么贪心法往往是易于描述的,易于实现的。
1、活动安排问题
设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交,则称活动i与活动j是相容的。也就是说,当si>=fj或sj>=fi时,活动i与活动j相容。
活动安排问题:要在所给的活动集合中选出最多的相容活动子集合。
活动安排问题的关键是如何按照一定的顺序安排活动,使得选出的活动间相容并能安排尽量多的活动。
例如:
按照活动结束时间非降序排序后结果如下:
由于活动以其结束时间的非减序排列,所以每次总是选择具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。
若被检查的活动i的开始时间si小于最近选择的活动j的结束时间fi,则不选择活动i,否则选择活动i加入集合A中。
贪心算法并不总能求得问题的整体最优解。但对于活动安排问题,贪心算法greedySelector却总能求得的整体最优解,即它最终所确定的相容活动集合A 的规模最大。
#define SIZE 11 //活动数量 typedef struct Activity //活动类型 { int id;//序号 int start;//开始时间 int finish;//结束时间 }Activity; //按结束时间非降序排序 //int Cmp_Act(const void* vp1, const void* vp2) //{ // return ((Activity*)vp1)->finish - ((Activity*)vp2)->finish; //} void Show(Activity* arr, int len) { for (int i = 0; i < len; i++) { printf("%d,%d,%d\n", arr[i].id, arr[i].start, arr[i].finish); } } //结束时间从小到大有序 bool LessFinish(Activity& elem1, Activity& elem2) { return elem1.finish < elem2.finish; } //arr:存放活动时间数据的数组 //len:arr的长度 //a:活动是否安排的标记,true安排,false不安排 int greedySelector(Activity* arr, int len, int* flg) { //qsort(arr, len, sizeof(Activity), Cmp_Act);//先按结束时间排序 sort(arr, arr + len, LessFinish); Show(arr, len); int i = 0;//当前安排的活动 int k = 0;//flg下标 flg[k++] = arr[0].id;//第一个活动总是加入 int count = 1;//安排活动的数量 for (int j = 1; j < len; j++) { if (arr[j].start >= arr[i].finish)//后面活动的开始时间晚于当前活动结束时间,需要加入 { flg[k++] = arr[j].id;//把当前活动序号加入 i = j; count++; } } return count; } int main() { Activity arr[SIZE] = { {1,0,6},{2,3,5},{3,1,4},{4,3,8},{5,5,9},{6,5,7},{7,6,10}, {8,2,13},{9,8,12},{10,8,11},{11,12,14} };//活动的时间情况 int flg[SIZE] = { 0 };//安排活动的序号存放的数组 int count = greedySelector(arr, SIZE, flg); printf("安排活动的序号是:"); for (int i = 0; i < count; i++) { printf("%d ", flg[i]); } return 0; }
2、最优装载问题
有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为wi,最优装载问题要求确定,在装载体积不受限制的情况下,应如何装载才能将尽可能多的集装箱装上轮船。该问题就是给出n个物体,第i个物体重量为wi,选择尽量多的物体,使得总重量不超过c。
分析
由于只关心物体的数量,所以装重的没有装轻的划算。只需要把所有的物体按重量从小到大排序,依次选择每个物体,直到装不下为止。这是一种典型的贪心算法,它只顾眼前,但却能得到最优解。
//最优装载问题:装尽可能多的物品 //arr:存放物品重量的数组 //n:数组的长度 //c:装载的最大重量 //只需要从最小重量的开始装载即可 //返回装载的物品数量 int MoreItems(int* arr, int len, int c) { std::sort(arr, arr + len);//排序 int count = 0;//统计物品数量 for (int i = 0; i < len; i++) { if (arr[i] <= c)//满足条件 { count++; c -= arr[i];//剩余装载的重量 } else//没有能装载的物品,但由于已经排序,无需继续遍历 { break; } } return count; } int main() { int arr[] = { 9,4,1,3,5,6,2,7,8 };//各类物品的重量 int c = 20;//最大装载量 int count = MoreItems(arr, sizeof(arr) / sizeof(arr[0]), c); printf("最多可以装载%d样物品\n", count); return 0; }
3、背包问题
有n个物体,第i个物体的重量为wi,价值为vi,在总重量不超过C的情况下让总价值尽量高,每一个物体都可以只取走一部分,价值和重量按比例计算。
分析
本题在上一题的基础上增加了价值,所以不能简单得像上题那样先拿轻的(轻的可能价值小),也不能先拿价值大的(可能它特别重),而应该综合考虑这两个因素。一种直观的贪心策略是:优先拿“性价比高的”,即“价值除以重量的值”最大的,直到重量和正好为C。
注意:由于每个物体可以只拿一部分,因此一定可以让总重量恰好为C(或者全部拿走重量也不足C),而且除了最后一个拿走的物体以外,所有的物体要么不拿,要么整个拿走。
例:有一个背包,背包容量是C=150。有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品价值最大,但不能超过总重量。
物品 | A | B | C | D | E | F | G |
重量 | 35 | 30 | 60 | 50 | 40 | 10 | 25 |
价值 | 10 | 40 | 30 | 50 | 35 | 40 | 30 |
//背包问题 // 物品结构体 typedef struct Item//商品 { int weight; // 重量 int value; // 价值 }Item; //性价比(价值/重量) bool cost_per(Item& it1, Item& it2) { return it1.value * 1.0 / it1.weight > it2.value * 1.0 / it2.weight; } //arr:存放商品的数组 //n:数组长度 //c:背包能承载的最大重量 double HighestValue(Item* arr, int n, int c) { //按“性价比”,价值/重量,降序排序 sort(arr, arr+n, cost_per); //验证按性价比排序成功 /*for (int i = 0; i < n; i++) { cout << arr[i].value * 1.0 / arr[i].weight << endl; }*/ double count = 0;//统计总价值 for (int i = 0; i < n; i++) { if (arr[i].weight <= c) { count += arr[i].value; c -= arr[i].weight;//剩余的装载量 printf("选择的物品%d,重量%d,价值%d\n", i + 1, arr[i].weight, arr[i].value); } else//只能拿部分 { count += (c * 1.0 / arr[i].weight) * arr[i].value; printf("选择的物品%d,重量%d,价值%d,只选择部分价值为%.2f\n", i + 1, arr[i].weight, arr[i].value, (c * 1.0 / arr[i].weight) * arr[i].value); break;//结束装载 } } return count; } int main() { Item arr[7] = { {35,10},{30,40 },{60,30}, {50,50},{40,35},{10,40},{25,30} }; int c = 150; double value = HighestValue(arr, sizeof(arr)/ sizeof(arr[0]), c); printf("能够装载的最高价值是:%.2f\n", value); return 0; }
4、乘船问题
有n个人,第i个人重量为wi。每艘船的最大载重量均为C,且最多只能乘两个人。用最少的船装载所有人。
分析
考虑最轻的人i,他应该和谁一起坐呢?如果每个人都无法和他一起坐船,则唯一的方案就是每个人坐一艘船。否则,他应该选择能和他一起坐船的人中最重的一个j人。这样的方法是贪心的,因此它只是让“眼前”的浪费最少。幸运的是,这个贪心策略也是对的,可以用反证法说明。
例如:现在有10个人,需要乘船,每艘船的最大载重为10,且最多只能乘两人,这10人的重量分别为4,2,1,3,5,6,8,7,10,9.请用最少的船装载所有人。
//乘船问题 int Cmp_int(const void* vp1, const void* vp2) { return *(int*)vp1 - *(int*)vp2; } //w:人的重量数组 //n:数组w的长度 //c:船的载重,且每艘船最多乘坐两人 //返回最少需要的船数 int Boat(int* w, int n, int c) { qsort(w, n, sizeof(int), Cmp_int);//人按重量升序排列 int count = 0;//船的数量 int i = 0;//排在前面最轻的人 int j = n - 1;//排在后面最重的人 while (n > 0)//还有人没有上船 { if (w[i] + w[j] > c)//如果最轻+最重>船的载重,最重的人需要单独乘船 { count++;//船的数量+1 j--;//最重的人单独乘船 n--;//已经有一个人乘船 } else//这两个人可以同乘一船 { count++; i++; j--; n -= 2;//乘船人少2 } } return count; } int main() { int w[10] = { 4,2,1,3,5,6,8,7,10,9 };//乘船人的重量 int c = 10;//船的载重 int count = Boat(w, sizeof(w) / sizeof(w[0]),c); printf("一共需要%d条船\n", count); return 0; }
力扣445、分发饼干
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子i,都有一个胃口值g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j,都有一个尺寸s[j]。如果s[j]>=g[i],我们可以将这个饼干j分配给孩子i,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
int Cmp_int(const void *vp1,const void *vp2) { return *(int*)vp1-*(int*)vp2; } int findContentChildren(int* g, int gSize, int* s, int sSize) { qsort(g,gSize,sizeof(int),Cmp_int); qsort(s,sSize,sizeof(int),Cmp_int); int count= 0;//满足的孩子数量 int i=0;//遍历孩子 int j=0;//遍历饼干 while(i<gSize && j<sSize) { while(j<sSize && g[i]>s[j])//找满足孩子胃口的饼干 { j++; } if(j>=sSize) { break; } //找符合条件的饼干 count++; i++;j++;//处理下一个孩子 } return count; }
利用STL的排序,代码如下:
class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(),g.end());//g是胃口值 sort(s.begin(),s.end());//s是饼干尺寸 int count=0;//计数器 int i=0;//g的下标 int j=0;//s的下标 for(;i<g.size();i++) { while(j<s.size() && s[j]<g[i])//不符合条件 { j++; } if(j==s.size()) { return count; } count++; j++; } return count; } };
力扣402、移掉K位数字
给你一个以字符串表示的非负整数num和一个整数k,移除这个数中的k位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
string removeKdigits(string num, int k) { string s;//新组建的字符串 s+=num[0]; int i = 1;//从第二个元素开始 while(i<num.size() && k>0) { if(s.size()>0&&s[s.size()-1]>num[i]) { s.erase(s.size()-1); k--; } else { //前面没有元素或者当前的比前面的大 s.push_back(num[i]); i++; } } while(k>0) { //直接删除尾部多余的元素 s.erase(s.size()-1); k--; } if(i<num.size()) { s+=string(num.begin()+i,num.end()); } while(s[0]=='0') s.erase(s.begin()); if(s.size()==0)//s是个空串 s="0"; return s; }
力扣409、最长回文串
给定一个包含大写字母和小写字母的字符串s,返回通过这些字母构造成的最长的回文串的长度。在构造过程中,请注意区分大小写。比如"Aa"不能当做一个回文字符串。
算法:
1、统计各字符串数量
使用一个unordered_map<char,int>(无序映射表)counter来统计字符串s中每个字符串出现的次数遍历字符串s中的每个字符c,并在counter中增加该字符的计数。
2、统计构造回文串的最大长度
初始化两个变量res和odd,res(用于记录回文子串的长度,不包括中心字符,如果有的话),odd(用于标记是否存在出现次数为奇数的字符,即回文中心字符),遍历counter中的每个键值对(kv),其中kv.first是字符,kv.second是该字符出现的次数,对于每个字符,计算其出现次数count,其确定该次数除以2的余数rem。由于回文子串的两侧是对称的,所以每个字符的偶数部分(count-rem)都可以完全用于构造回文子串。这部分长度加到res上。如果rem等于1,说明该字符出现次数为奇数,它可以在回文子串的中心位,(如果只有一个期数频率的字符,或者作为两个奇数频率字符之间的桥梁),因此将odd置为1
3、计算并返回最长回文子串的长度
最终,最长回文子串的长度由res(偶数频率字符贡献的长度)和odd(是否存在奇数频率字符)共同决定。如果odd为1,说明存在至少一个字符可以作为回文中心,因此最长回文子串的长度为res+1;如果odd为0,说明所有字符的出现次数都是偶数,最长回文子串的长度就是res。但由于代码中将odd的初始值设置为0,并且在遇到奇数频率的字符时将其设置为1,所以最后只需将res和odd相加即可得到最长回文子串的长度(因为odd的值要么是0,要么是1)。
int longestPalindrome(string s) { // 统计各字符数量 unordered_map<char, int> counter; for (char c : s) counter[c]++; // 统计构造回文串的最大长度 int res = 0, odd = 0; for (auto kv : counter) { // 将当前字符出现次数向下取偶数,并计入 res int count = kv.second; int rem = count % 2; res += count - rem; // 若当前字符出现次数为奇数,则将 odd 置 1 if (rem == 1) odd = 1; } return res + odd;
力扣11、盛最多水的容器
给定一个长度为n的整数数组height。有n条垂线,第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
算法思路:
1、初始化两个指针i和j分别指向数据height的起始位置和结束位置。
2、初始化一个变量res来记录找到的最大面积(即盛最多水的容器)
3、使用一个while循环,当i<j时执行循环体。
4、在每次循环中,比较height[i]和height[j]的大小,选择较小的那个高度,并计算以这个高度为高的矩形的面积(即(j-i)*height[较小的柱子]),然后将这个面积与当前的最大面积res进行比较,更新res当i和j相遇时,循环结束,此时res中存储的就是能够盛最多水的容器。
int maxArea(vector<int>& height) { int i=0,j=height.size()-1,res=0; while(i<j) { res=height[i]<height[j]? max(res,(j-i)*height[i++]): max(res,(j-i)*height[j--]); } return res; }
力扣581、最短无序连续子数组
给你一个整数数组nums,你需要找出一个连续子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
请你找出符合题意的最短子数组,并输出它的长度。
算法1:
1、从左到右遍历:
我们维护一个max_left变量来跟踪到目前为止遍历过的元素中的最大值。如果遇到一个元素小于max_left,则更新end为当前索引。这个end将是未排序子数组的右边界(或最后一个元素的索引)
2、从右到左遍历:
我们维护一个min_right变量来跟踪到目前为止遍历过的元素中的最小值。如果遇到一个元素大于min_right,则更新begin为当前索引。这个begin将是未排序字数组的左边界(或第一个元素的索引)
3、返回值
如果end仍然是初始值-1,说明整个数组已经是非递减的,返回0.否则,返回end-begin+1,即需要重新排序的子数组的长度。
int findUnsortedSubarray(vector<int>& nums) { int len=nums.size(); if(len<=1) { return 0;//如果数组长度小于等于1,则无需排序 } //从左到右遍历,找到第一个破环非递减顺序的元素及其应该处于的位置 int max_left=nums[0]; int end=-1; for(int i=1;i<len;++i) { if(nums[i]<max_left) { end=i; } else { max_left=nums[i]; } } if(end==-1)//如果end仍然是-1,说明整个数组已经是非递减的 { return 0; } //从右到左遍历,找到第一个破坏非递减顺序的元素(向左看)及其应该处于的位置 int min_right=nums[len-1]; int begin=len; for(int i=len-2;i>=0;--i) { if(nums[i]>min_right) { begin=i; } else { min_right=nums[i]; } } //返回需要重新排序的子数组的长度 return end-begin+1;
算法2:
vector<int>v=nums;//复制数据 sort(v.begin(),v.end());//排序 int start=0; int end=nums.size()-1; //找第一个不同点 while(start<=end) { if(v[start]!=nums[start])//找到了 break; start++; } if(start>end)//没找到 return 0; while(end>=0) { if(v[end]!=nums[end]) break; end--; } return end-start +1;
力扣605、种花问题
假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给你一个整数数组flowerbed表示花坛,由若干0和1组成,其中0表示没种植花,1表示种植了花。另有一个数n,能否在不打破种植规则的情况下种入n朵花?能则返回true,不能则返回false。
算法:
1、预处理
为了简化边界条件的处理,在flowerbed数组开头的结尾各插入了一个0(代表空地),这样在遍历数组时,就不需要特别检查第一个和最后一个元素是否可以种花,因为它们都被视为空地。
2、遍历数组
从数组的第二个元素(索引为1,因为已经插入了一个0作为第一个元素)开始,到倒数第二个元素结束(因为最后一个元素后面也插入了一个0),遍历整个flowerbed数组。
3、检查种花条件
对于遍历到的每个位置(索引为i),检查它是否满足种花的条件:即它本身(flowerbed[i])是空地(0),并且它的前一个位置(flowerbed[i-1])和后一个位置(flowerbed[i+1)也都是空地,这是通过比较这三个位置的值是否都为0来实现的。
4、种花
如果当前位置满足种花的条件,那么在该位置种下一朵话(即将flowerbed[i]的值改为1),并减少还需要种的花的数量n。
5、检查是否完成
遍历完成后,检查还需要种的花的数量n是否小于或等于0.如果是,说明已经种够了或者超过了所需的花的数量,函数返回true;否则,返回false。
bool canPlaceFlowers(vector<int>& flowerbed, int n) { flowerbed.insert(flowerbed.begin(), 0); flowerbed.push_back(0); for (int i = 1; i < flowerbed.size()-1; i++) { if (flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0) { flowerbed[i] = 1; // 种花! n--; } } return n <= 0;