기술나눔

"알고리즘 노트" 요약 6번 - Greedy

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. 단순한 욕심

        탐욕스러운 방법일종의 해결방법이다최적화 문제 이 방법은 항상 현재 상태에서 로컬 최적(또는 더 나은) 이후 최적(또는 더 나은) 전역 결과를 달성하기 위한 전략을 고려합니다. 분명히 더 좋지만 최적이 아닌 전략이 채택되면(최적 전략이 존재하지 않거나 생각하기 쉽지 않음) 얻은 전체 결과는 최적이 될 수 없습니다.최적의 결과를 얻기 위해서는 각 중간 단계 전략이 최적이어야 하므로 이를 해결하기 위해 그리디 방법을 엄격하게 사용합니다.최적화하다 이 질문에는 채택된 전략의 정당성이 필요합니다. 증명의 일반적인 개념은 모순과 수학적 귀납법에 의한 증명을 사용하는 것, 즉 전략이 최적의 해로 이어질 수 없다고 가정하고 일련의 도출을 통해 모순을 얻어 전략이 최적임을 증명하는 것입니다. , 마지막으로 수학적 귀납법을 사용하여 전역 최적을 보장합니다. 하지만 일상생활에서 생각나는 전략을 엄밀하게 증명하는 것은 시간이 걸리거나 쉽지 않을 수 있으므로(탐욕 자체보다 탐욕의 증명이 더 어려운 경우가 많습니다) 일반적으로 말해서 실현 가능해 보이는 전략을 생각해보면, 그리고 반례를 제시할 수 없다면 용기를 갖고 이를 구현해 보세요.

1. 가장 작은 숫자를 그룹화

0부터 9까지의 숫자가 주어지면 이 숫자를 어떤 순서로든 배열할 수 있지만 모두 사용해야 하며 대상 숫자를 최대한 작게 만들어야 합니다(물론 0이 첫 번째가 될 수는 없습니다). 0이 2개, 1이 2개, 5가 3개, 8이 있는데, 얻은 가장 작은 숫자는 100155858입니다.

전략은 단번에 알 수 있다고 생각합니다. 먼저 1부터 9까지 0이 아닌 가장 작은 숫자를 선택하여 출력한 다음 0부터 9까지의 숫자를 출력합니다. 각 숫자가 출력되는 횟수는 남은 숫자입니다.

올바른 전략의 증명：

  • 우선, 조합에는 모든 숫자가 참여해야 하므로 최종 결과의 자릿수가 결정됩니다.
  • 가장 높은 비트는 0이 아니므로 첫 번째 비트만큼 가능한 작은 숫자를 선택하라 - 최상위 비트 정리
  • 나머지 숫자도 작은 것부터 큰 것으로 출력해야죠~

교과서는 너무 추상적이어서 약간 잘못된 것 같습니다. 여기서 블로거는 다음과 같이 썼습니다.

  1. #include <cstdio>
  2. #include <vector>
  3. #include <iostream> 
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int main() {	
  8. 	vector<int> V;
  9. 	for(int i=1;i<=10;i++)
  10. 	{
  11. 		int temp=0;
  12. 		cin>>temp;
  13. 		V.push_back(temp);
  14. 	}
  15. 	sort(V.begin(),V.end());  //直接排成升序 
  16. 	int flag=0;  //标记 
  17. 	for(int i=0;i<=9;i++)
  18. 		if(V[i]!=0)
  19. 		{
  20. 			int temp=V[i];
  21. 			V[i]=V[0];
  22. 			V[0]=temp;
  23. 			flag=i;//保存第一个不为0的位置 
  24. 			break;	
  25. 		}
  26. 	for(int i=flag+1;i<=9;i++)  //找更小的头，直接从flag下一位开始即可，节省时间~ 
  27. 		if(V[i]<V[0]&&V[i]!=0)
  28. 		{
  29. 			int temp=V[i];
  30. 			V[i]=V[0];
  31. 			V[0]=temp;
  32. 		}
  33. 	for(int i=0;i<=9;i++)
  34. 		cout<<V[i];
  35. }

논리적으로는 어렵지 않아요, 명료하게 생각하는 게 중요해요~

2.월병 인벤토리

  • 입력: 첫 번째 줄에 N과 M을 입력합니다. N자리 월병 유형 수와 M자리 월병에 대한 시장 수요는 다음 두 줄에 입력해야 합니다. 첫 번째 줄의 N 숫자는 다음과 같습니다. 현재 종류는 월병을 모두 팔면 얼마를 벌 수 있는지, 그리고 두 번째 줄의 N 숫자는 현재 월병의 총 개수에 해당됩니다~
  • 필수 산출물: 특정 수요에 따른 최대 소득

당신이 상사라면 어떻게 "욕심"이 생길지 상상해보십시오. 당연하게도 제한된 수요 내에서 단가가 가장 높은 월병을 최대한 많이 팔기만 하면 가장 많은 매출을 올릴 수 있지 않을까요? 블로거가 직접 작성한 다음 구현은 교과서의 구현과 다릅니다.

  1. #include <cstdio>
  2. #include <vector>
  3. #include <iostream> 
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. struct mooncake{
  8. 	double num;  //总数 
  9. 	double income;  //总收入 
  10.  	double price;   //单价，需要自己计算 
  11. }; 
  12.  
  13. int main() {
  14. 	int N,M;
  15. 	cin>>N>>M;
  16. 	vector<mooncake> V;
  17. 	for(int i=1;i<=N;i++) 
  18. 	{
  19. 		mooncake temp;
  20. 		V.push_back(temp);
  21. 	}
  22. 	cout<<"请输入数量："<<endl;
  23. 	for(int i=1;i<=N;i++) 
  24. 	{
  25. 		double num=0;
  26. 		cin>>num;
  27. 		V[i-1].num=num;
  28. 	}
  29. 	cout<<"请输入总价："<<endl;
  30. 	for(int i=1;i<=N;i++) 
  31. 	{
  32. 		double income=0;
  33. 		cin>>income;
  34. 		V[i-1].income=income;
  35. 	}
  36. 	for(int i=0;i<=N-1;i++) 
  37. 		V[i].price=V[i].income/V[i].num; //计算单价
  38. 	//按单价降序排列！保证贵的尽可能多卖
  39. 	
  40. 	for(int i=0;i<=V.size()-1;i++)
  41. 	{
  42. 		for(int j=i;j<=V.size()-1;j++)    
  43. 			if(V[j].price>V[i].price)    
  44. 			{
  45. 				mooncake temp;
  46. 				temp=V[j];
  47. 				V[j]=V[i];
  48. 				V[i]=temp;
  49. 			}
  50. 	}
  51. 	for(int i=0;i<=V.size()-1;i++)
  52. 		cout<<"单价第"<<(i+1)<<"高的值为："<<V[i].income<<" "<<V[i].price<<" "<<V[i].num<<endl;
  53. 	
  54. 	
  55. 	for(int i=0;i<=N-1;i++)
  56. 		cout<<V[i].num<<endl; 
  57. 	int j=0;  //使用的下标 
  58. 	double count=0;  //总利润 
  59. 	while(M>0)  //当还有需求量时 
  60. 	{
  61. 		double doubt=0;
  62. 		doubt=M-V[j].num; //用M减去当前类型的额总量 
  63. 		if(doubt>=0)//减了以后M还有剩余
  64. 		{
  65. 			M-=V[j].num;//当前种类全部卖出 
  66. 			count+=V[j].income;//直接总价相加 
  67. 			j++;
  68. 			cout<<V[j].num;
  69. 		}
  70. 		else if(doubt<0) //不够减这么多
  71. 		{
  72. 			count+=V[j].price*M;//剩余部分按照单价计算 
  73. 			break; 
  74. 		} 
  75. 	}
  76. 	cout<<"最高利润值为："<<count<<endl;
  77. 	return 0;
  78. }

위의 Whlie 루프를 주의 깊게 맛보십시오. M이 0이 아닌 경우, 즉 여전히 수요가 있는 경우 가장 비싼 월병을 판매하십시오. 순서대로 하나씩 판매: 현재 수요가 현재 유형을 모두 판매하기에 충분할 경우 총 가격이 직접 추가됩니다. 현재 유형을 모두 판매하기에 충분하지 않으면 거기에 있는 만큼 판매합니다. 단가를 기준으로 계산해 보세요~

교과서의 테스트 사례를 사용하여 테스트해 보겠습니다.

  • 3 20
  • 18 15 10
  • 75 72 45

결과는 94.50으로 표준답안과 일치합니다~

게다가 여기 블로거님은 정렬을 메인함수에 직접 작성하시고, 독립된 함수로 작성하신 후 호출하시는데, 구조체형 벡터에 버그가 있는 것 같은데, 알면 정렬이 성공하지 못하는군요. 이유는 댓글란에 적어주시면 됩니다~

2. 간격 욕심

질문의 내용은 다음과 같습니다.

이런 유형의 질문에 대해서는 다음 사항만 기억하면 됩니다.왼쪽 끝점이 더 큰 간격에 우선 순위를 부여합니다.！

 

위 그림처럼 왜 이렇게 하는지 이야기해보겠습니다. 찾기는 어렵지 않습니다.가능한 한 많은 선택을 보장하기 위해 긴 간격에 짧은 간격이 포함된 경우 가장 짧은 간격을 먼저 선택해야 합니다., 이것은 이해하기 쉽습니다.

위와 같은 상황에서 1과 2처럼 간격이 겹치는 경우 왼쪽 끝점이 가장 큰 간격 1을 선택하면 위치 9만 점유하고 간격 2를 선택하면 위치 9만 점유하는 것을 어렵지 않게 찾을 수 있습니다. 위치 8. 위치 - 이는 욕심을 부리고 최대한 적은 돈을 쓴다(공간을 적게 쓴다)는 생각과 확실히 맞지 않으므로 최대한 왼쪽으로 선택해야 빈 공간이 더 많아진다. 오른쪽 ~ 위와 같이손으로 계산해 보면 최대 4개의 분리된 항목이 있음을 알 수 있습니다.

교과서의 코드:

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. const int maxn=110;
  6. struct Inteval{
  7. 	int x,y;  //开区间左右端点 
  8. }I[maxn]; 
  9.  
  10. bool cmp(Inteval a,Inteval b)
  11. {
  12. 	if(a.x!=b.x)
  13. 		return a.x>b.x;   //左端点从大到小排序 
  14. 	else
  15. 		return a.y<b.y;   //左端点相同的按右端点从小到大排序 
  16. }
  17.  
  18. int main() {
  19. 	int n;
  20. 	while(scanf("%d",&n,n!=0))
  21. 	{
  22. 		for(int i=0;i<n;i++)
  23. 			scanf("%d%d",&I[i].x,&I[i].y);
  24. 		sort(I,I+n,cmp); //排序区间 
  25. 		int ans=1,lastX=I[0].x;
  26. 		//ans记录总数，lastX记录上一个被选择的区间的左端点 
  27. 		for(int i=1;i<n;i++)
  28. 		{
  29. 			if(I[i].y<=lastX)   //如果该区间右端点在lastX左边 
  30. 			{
  31. 				lastX=I[i].x;  //以I[i]作为新选中的区间 
  32. 				ans++;   //不相交的区间个数+1 
  33. 			}	
  34. 		}
  35. 		printf("%dn",ans);	
  36. 	} 
  37. 	return 0;
  38. }

그러나 블로거들은 여전히 ​​원본 배열을 좋아하지 않습니다. 다음은 벡터 구조 버전입니다.

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. struct section{
  7. 	int x=0;
  8. 	int y=0;
  9. 	//x和y分别为左右端点 
  10. }; 
  11.  
  12.  
  13. int main() {
  14. 	int n=0;
  15. 	vector<section> V;
  16. 	cin>>n;
  17. 	for(int i=1;i<=n;i++) //读入数据 
  18. 	{
  19. 		section temp;
  20. 		int x=0,y=0;
  21. 		cin>>x>>y;
  22. 		if(x>y)   //防止左端点大于右端点 
  23. 		{
  24. 			int temp1=x;
  25. 			x=y;
  26. 			y=temp1;	
  27. 		}
  28. 		else if(x==y) //若左右端点相同 
  29. 		{
  30. 			i-=1;  //则当前输入 不算
  31. 			cout<<"不可以输入相同的左右端点！"<<endl; 
  32. 			continue;  //舍弃数据，本次循环作废~ 
  33. 		}	
  34. 		temp.x=x;
  35. 		temp.y=y;
  36. 		V.push_back(temp);
  37. 	}
  38. 	//按要求排序区间优先级 
  39. 	for(int i=0;i<=V.size()-1;i++)
  40. 	{
  41. 		for(int j=i+1;j<=V.size()-1;j++)
  42. 		{
  43. 			if(V[j].x>V[i].x)  //左端点越大越靠前
  44. 			{
  45. 				section temp=V[j];
  46. 				V[j]=V[i];
  47. 				V[i]=temp;
  48. 			}
  49. 			else if(V[j].x==V[i].x&&V[j].y<V[i].y) //左端点相同的话，右端点小的优先 
  50. 			{
  51. 				section temp=V[j];
  52. 				V[j]=V[i];
  53. 				V[i]=temp;
  54. 			} 
  55. 		}
  56. 	}
  57. 	cout<<"顺序如下："<<endl; 
  58. 	for(int i=0;i<=V.size()-1;i++)
  59. 		cout<<V[i].x<<"~"<<V[i].y<<endl; 
  60. 	int count=1,lastX=V[0].x;
  61. 	//count用来统计总数，lastX是上一个符合条件的区间的左端点
  62. 	 
  63. 	for(int i=1;i<=V.size()-1;i++)//直接从第二个区间开始 
  64. 	{
  65. 		if(V[i].y<lastX)  //如果当前区间的右端点不和上一个左端点相加，满足题意 
  66. 		{
  67. 			lastX=V[i].x;
  68. 			count++;
  69. 		}		
  70. 	} 
  71. 	cout<<count<<endl;
  72. 	return 0;
  73. }

테스트는 다음과 같습니다.

 

일반적으로 그리디(Greedy) 방법은 일종의 최적화 문제를 해결하기 위해 사용되는 알고리즘 아이디어로, 로컬 최적 전략으로부터 전역 최적 결과를 도출하기를 희망합니다.그리디 알고리즘 적용 가능한 문제는 최적 하위 구조의 속성을 충족해야 합니다. 즉, 문제의 최적 솔루션은 하위 문제의 최적 솔루션으로부터 효과적으로 구성될 수 있습니다. 분명히 모든 문제가 그리디 방법에 적합한 것은 아니지만 이것이 그리디 알고리즘이 간단하고 실용적이며 효율적인 알고리즘이 되는 것을 방해하지는 않습니다~

개인 프로필

그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에서 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편