Condivisione della tecnologia

"Note sull'algoritmo" Riepilogo n. 6 - Greedy

2024-07-12

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

1. Avidità semplice

        metodo golosoÈ una sorta di soluzioneProblema di ottimizzazione Questo metodo considera sempre la strategia per ottenere il risultato globale ottimale (o migliore) dopo l'ottimo locale (o migliore) nello stato attuale. Ovviamente, se si adotta una strategia migliore ma non ottimale (la strategia ottimale può non esistere o non è facile pensarla), il risultato globale ottenuto non potrà essere ottimale.Per ottenere il risultato ottimale, è necessario che ogni strategia di passaggio intermedio sia ottimale, quindi il metodo goloso viene utilizzato rigorosamente per risolvere il problema.ottimizzare La questione richiede la giustificazione della strategia adottata. L'idea generale della dimostrazione è quella di utilizzare la dimostrazione per contraddizione e induzione matematica, cioè assumendo che la strategia non possa portare alla soluzione ottima, e quindi ottenere la contraddizione attraverso una serie di derivazioni per dimostrare che la strategia è ottimale , e infine utilizzare l'induzione matematica per garantire l'ottimo globale. Tuttavia, per l'uso quotidiano, potrebbe non essere il momento o la facilità per dimostrare rigorosamente la strategia che ti viene in mente (la prova dell'avidità è spesso più difficile dell'avidità stessa), quindi in generale, se pensi a una strategia che sembra fattibile, E se non puoi fornire un controesempio, sii abbastanza coraggioso da metterlo in pratica.

1. Raggruppa il numero più piccolo

Dato un numero di numeri da 0 a 9, puoi disporre questi numeri in qualsiasi ordine, ma devi usarli tutti e rendere il numero di destinazione il più piccolo possibile (ovviamente, 0 non può essere il primo Ad esempio, inserisci). due 0, due 1, tre 5 e un 8, il numero più piccolo ottenuto è 100155858.

Credo che tu possa vedere subito la strategia: seleziona prima il numero più piccolo che non è 0 da 1 a 9 per l'output, quindi emetti i numeri da 0 a 9. Il numero di volte in cui ciascun numero viene visualizzato è il suo numero rimanente.

Prova della strategia corretta：

  • Innanzitutto, poiché tutti i numeri devono partecipare alla combinazione, viene determinato il numero di cifre del risultato finale.
  • Poiché il bit più alto non è 0, scegli un numero il più piccolo possibile come primo bit: il teorema del bit più alto
  • Anche le restanti cifre dovrebbero essere emesse da piccole a grandi~

Quello nel libro di testo è davvero troppo astratto e sembra un po' sbagliato. Qui lo ha scritto lui stesso:

  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. }

Logicamente non è difficile, l’importante è pensare chiaramente~

2. Inventario della torta lunare

  • Input: inserisci N e M nella prima riga: il numero di tipi di mooncake a N cifre e la domanda di mercato a M cifre per i mooncake devono essere inseriti nelle due righe successive: i numeri N nella prima riga corrispondono a i tipi attuali Quanto puoi guadagnare dopo aver venduto tutti i mooncakes, e il numero N nella seconda riga corrisponde al numero totale attuale di mooncakes~
  • Produzione richiesta: reddito massimo sotto una domanda specifica

Immagina se tu fossi il capo, come saresti "avido"? Ovviamente, se avessi solo bisogno di vendere quanti più mooncakes al prezzo unitario più costoso possibile entro una domanda limitata, non sarebbe possibile ottenere il maggior fatturato? Quella che segue è un'implementazione scritta dallo stesso blogger, che è diversa da quella del libro di testo:

  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. }

Assaggia attentamente il ciclo whlie sopra: quando M non è 0, cioè c'è ancora domanda, vendi i mooncakes più costosi. Vendere uno per uno in ordine: se la domanda attuale è sufficiente per esaurire tutti i tipi attuali, il prezzo totale verrà aggiunto direttamente, se non è sufficiente per esaurire tutti quelli attuali, venderne quanti ce ne sono; sono e calcolano in base al prezzo unitario~

Proviamolo con il test case del libro di testo:

  • 3 20
  • 18 15 10
  • 75 72 45

Il risultato è 94,50, che è coerente con la risposta standard~

Inoltre, il blogger qui scrive direttamente l'ordinamento nella funzione principale, lo scrive in una funzione indipendente e poi lo chiama Sembra che ci sia un bug nel vettore del tipo di struttura e l'ordinamento non ha esito positivo motivo, puoi scriverlo nell'area commenti~

2. Intervallo goloso

La radice della domanda è la seguente:

Per questo tipo di domande, devi solo ricordare——Dai la priorità all'intervallo con il punto finale sinistro più grande！

 

Parliamo del perché lo facciamo, come mostrato nella foto sopra: non è difficile da trovare,Per garantire quante più scelte possibili, quando un intervallo più lungo contiene un intervallo più breve, dobbiamo selezionare prima l'intervallo più breve, questo è facile da capire.

Per la situazione di cui sopra, come intervalli sovrapposti come 1 e 2, non è difficile scoprire che se si seleziona l'intervallo 1 con il punto finale sinistro più grande, occuperà solo la posizione 9, mentre se si seleziona l'intervallo 2, occuperà posizione 8. Posizione - Questo ovviamente non è in linea con l'idea di spendere meno soldi possibile (spendere meno spazio), quindi dovresti scegliere il più a sinistra possibile, in modo che ci siano più spazi vuoti a destra ~ come sopra,Possiamo vedere facendo calcoli a mano che ce ne sono al massimo 4 disgiunti.

Codice dal libro di testo:

  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. }

Tuttavia, ai blogger non piacciono ancora gli array originali. Ecco una versione con struttura vettoriale:

  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. }

La prova è la seguente:

 

In generale, il metodo greedy è un'idea algoritmica utilizzata per risolvere un tipo di problema di ottimizzazione e spera di derivare il risultato ottimale globale da una strategia ottimale locale.algoritmo avido I problemi applicabili devono soddisfare le proprietà della sottostruttura ottimale, cioè la soluzione ottima di un problema può essere effettivamente costruita dalle soluzioni ottime dei suoi sottoproblemi. Ovviamente non tutti i problemi sono adatti al metodo greedy, ma questo non impedisce all'algoritmo greedy di diventare un algoritmo semplice, pratico ed efficiente~

Profilo personale

Si dedica alla ricerca tecnologica da più di 30 anni ed è esperto in vari linguaggi come Java, Linux, Javascript, php, css, ecc. Ha dato numerosi contributi nel campo dell'open source stazione di documentazione per gli sviluppatori per condividere alcuni problemi nello sviluppo della tecnologia per riferimento futuro

le mie informazioni di contatto

Posta