Summary of Algorithm Notes No.6

Summary of Algorithm Notes No.6: Greedy

2024-07-12

1. Simple Greedy

Greedy MethodIt is a kind of solutionOptimization ProblemThe method always considers the strategy of making the global result reach the optimal (or better) after the local optimal (or better) in the current state. Obviously, if a better strategy is adopted instead of the optimal one (the optimal strategy may not exist or is not easy to think of), the global result obtained cannot be the optimal one. To obtain the optimal result, it is required that each step strategy in the middle is the optimal one, so the greedy method is strictly used to solve it.optimizeThe problem requires proof of the adopted strategy. The general idea of proof is to use proof by contradiction and mathematical induction, that is, assuming that the strategy cannot lead to the optimal solution, and then obtain the contradiction through a series of deductions to prove that the strategy is optimal, and finally use mathematical induction to ensure the global optimality. However, for ordinary use, there may not be time or it may not be easy to rigorously prove the strategy you think of (the proof of greed is often more difficult than greed itself), so generally speaking, if you think of a strategy that seems feasible and you cannot give a counterexample, then bravely implement it.

1. Minimum number of groups

Given a number of numbers from 0 to 9, you can arrange these numbers in any order, but you must use all of them and make the target number as small as possible (of course 0 cannot be the first number). For example, if you input two 0s, two 1s, three 5s and one 8, the minimum number you get is 100155858.

I believe you can see the strategy at once: first select the smallest non-zero number from 1 to 9 and output it, then output numbers from 0 to 9, and output each number the same number of times as the remaining number.

Proof of correct strategy：

First of all, since all numbers must participate in the combination, the number of digits in the final result is fixed.
Since the highest bit is not 0, choose a number as small as possible as the first bit - the highest bit theorem
The remaining digits should also be output from small to large~

The textbook is too abstract and seems to be a bit wrong. Here is one that the blogger wrote himself:


#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;
 
int main() {	
	vector<int> V;
	for(int i=1;i<=10;i++)
	{
		int temp=0;
		cin>>temp;
		V.push_back(temp);
	}
	sort(V.begin(),V.end());  //直接排成升序 
	int flag=0;  //标记 
	for(int i=0;i<=9;i++)
		if(V[i]!=0)
		{
			int temp=V[i];
			V[i]=V[0];
			V[0]=temp;
			flag=i;//保存第一个不为0的位置 
			break;	
		}
	for(int i=flag+1;i<=9;i++)  //找更小的头，直接从flag下一位开始即可，节省时间~ 
		if(V[i]<V[0]&&V[i]!=0)
		{
			int temp=V[i];
			V[i]=V[0];
			V[0]=temp;
		}
	for(int i=0;i<=9;i++)
		cout<<V[i];
}

There is no difficulty in logic, the main thing is to think clearly~

2. Mooncake Inventory

Input: Enter N and M in the first line: N is the number of mooncake types, and M is the total market demand for mooncakes; the next two lines need to enter N numbers: the N numbers in the first line correspond to how much you can earn after all the current types of mooncakes are sold, and the N numbers in the second line correspond to the total number of mooncakes currently.
Required output: Maximum income under specified demand

Imagine if you were a boss, how would you be "greedy"? Obviously - you just need to sell as many mooncakes with the highest price as possible within the limited demand, wouldn't that mean you can get the most sales? The following is an implementation written by the blogger himself, which is also different from the textbook:


#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;
 
struct mooncake{
	double num;  //总数 
	double income;  //总收入 
 	double price;   //单价，需要自己计算 
}; 
 
int main() {
	int N,M;
	cin>>N>>M;
	vector<mooncake> V;
	for(int i=1;i<=N;i++) 
	{
		mooncake temp;
		V.push_back(temp);
	}
	cout<<"请输入数量："<<endl;
	for(int i=1;i<=N;i++) 
	{
		double num=0;
		cin>>num;
		V[i-1].num=num;
	}
	cout<<"请输入总价："<<endl;
	for(int i=1;i<=N;i++) 
	{
		double income=0;
		cin>>income;
		V[i-1].income=income;
	}
	for(int i=0;i<=N-1;i++) 
		V[i].price=V[i].income/V[i].num; //计算单价
	//按单价降序排列！保证贵的尽可能多卖
	
	for(int i=0;i<=V.size()-1;i++)
	{
		for(int j=i;j<=V.size()-1;j++)    
			if(V[j].price>V[i].price)    
			{
				mooncake temp;
				temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			}
	}
	for(int i=0;i<=V.size()-1;i++)
		cout<<"单价第"<<(i+1)<<"高的值为："<<V[i].income<<" "<<V[i].price<<" "<<V[i].num<<endl;
	
	
	for(int i=0;i<=N-1;i++)
		cout<<V[i].num<<endl; 
	int j=0;  //使用的下标 
	double count=0;  //总利润 
	while(M>0)  //当还有需求量时 
	{
		double doubt=0;
		doubt=M-V[j].num; //用M减去当前类型的额总量 
		if(doubt>=0)//减了以后M还有剩余
		{
			M-=V[j].num;//当前种类全部卖出 
			count+=V[j].income;//直接总价相加 
			j++;
			cout<<V[j].num;
		}
		else if(doubt<0) //不够减这么多
		{
			count+=V[j].price*M;//剩余部分按照单价计算 
			break; 
		} 
	}
	cout<<"最高利润值为："<<count<<endl;
	return 0;
}

Carefully appreciate the above-mentioned "Whlie" loop: When M is not 0, that is, there is still demand, sell the most expensive mooncakes. Sell them one by one in order: If the current demand is enough to sell all the quantities of the current type, simply add up the total price; if it is not enough to sell all the current ones, sell as many as you have and calculate according to the unit price~

Let's test the test case in the textbook:

3 20
18 15 10
75 72 45

The result is 94.50, which is consistent with the standard answer~

In addition, the blogger here directly wrote the sorting in the main function, and wrote it in an independent function and then called it. There seems to be a bug for the vector of structure type, and the sorting is not very successful. If you know the reason, please write it in the comment area~

2. Interval Greedy

The title is as follows:

For this type of question, just remember:Prioritize intervals with large left endpoints！

Let's talk about why we do this, as shown in the figure above: It is not difficult to find thatIn order to ensure as many choices as possible, when a longer interval contains a shorter interval, we must first select the shortest interval., this is easy to understand.

For the above situation, such as overlapping intervals 1 and 2, it is not difficult to find that if you choose the interval 1 with the largest left endpoint, it will only occupy the 9th position, while if you choose the interval 2, it will occupy the 8th position - this is obviously not in line with the idea of greedy spending as little money as possible (spending as few intervals as possible), so you should choose as far to the left as possible, so that there will be more space on the right ~ as above,We can see by hand calculation that there are at most 4 non-intersecting ones.

Code from the textbook:


#include <cstdio>
#include <algorithm>
using namespace std;
 
const int maxn=110;
struct Inteval{
	int x,y;  //开区间左右端点 
}I[maxn]; 
 
bool cmp(Inteval a,Inteval b)
{
	if(a.x!=b.x)
		return a.x>b.x;   //左端点从大到小排序 
	else
		return a.y<b.y;   //左端点相同的按右端点从小到大排序 
}
 
int main() {
	int n;
	while(scanf("%d",&n,n!=0))
	{
		for(int i=0;i<n;i++)
			scanf("%d%d",&I[i].x,&I[i].y);
		sort(I,I+n,cmp); //排序区间 
		int ans=1,lastX=I[0].x;
		//ans记录总数，lastX记录上一个被选择的区间的左端点 
		for(int i=1;i<n;i++)
		{
			if(I[i].y<=lastX)   //如果该区间右端点在lastX左边 
			{
				lastX=I[i].x;  //以I[i]作为新选中的区间 
				ans++;   //不相交的区间个数+1 
			}	
		}
		printf("%dn",ans);	
	} 
	return 0;
}

However, the blogger still doesn't like the original array. Here is a vector structure version:


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct section{
	int x=0;
	int y=0;
	//x和y分别为左右端点 
}; 
 
 
int main() {
	int n=0;
	vector<section> V;
	cin>>n;
	for(int i=1;i<=n;i++) //读入数据 
	{
		section temp;
		int x=0,y=0;
		cin>>x>>y;
		if(x>y)   //防止左端点大于右端点 
		{
			int temp1=x;
			x=y;
			y=temp1;	
		}
		else if(x==y) //若左右端点相同 
		{
			i-=1;  //则当前输入 不算
			cout<<"不可以输入相同的左右端点！"<<endl; 
			continue;  //舍弃数据，本次循环作废~ 
		}	
		temp.x=x;
		temp.y=y;
		V.push_back(temp);
	}
	//按要求排序区间优先级 
	for(int i=0;i<=V.size()-1;i++)
	{
		for(int j=i+1;j<=V.size()-1;j++)
		{
			if(V[j].x>V[i].x)  //左端点越大越靠前
			{
				section temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			}
			else if(V[j].x==V[i].x&&V[j].y<V[i].y) //左端点相同的话，右端点小的优先 
			{
				section temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			} 
		}
	}
	cout<<"顺序如下："<<endl; 
	for(int i=0;i<=V.size()-1;i++)
		cout<<V[i].x<<"~"<<V[i].y<<endl; 
	int count=1,lastX=V[0].x;
	//count用来统计总数，lastX是上一个符合条件的区间的左端点
	 
	for(int i=1;i<=V.size()-1;i++)//直接从第二个区间开始 
	{
		if(V[i].y<lastX)  //如果当前区间的右端点不和上一个左端点相加，满足题意 
		{
			lastX=V[i].x;
			count++;
		}		
	} 
	cout<<count<<endl;
	return 0;
}

The test is as follows:

In general, the greedy method is an algorithmic idea used to solve a class of optimization problems, hoping to deduce the global optimal result from the local optimal strategy.Greedy AlgorithmApplicable problems must satisfy the properties of optimal substructure, that is, the optimal solution to a problem can be effectively constructed from the optimal solutions to its subproblems. Obviously, not all problems are suitable for the greedy method, but this does not prevent the greedy algorithm from becoming a simple, practical and efficient algorithm.

Technology Sharing