Compartilhamento de tecnologia

Resumo nº 6 das "Notas de algoritmo" - Ganancioso

2024-07-12

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

1. Ganância simples

        método gananciosoÉ uma espécie de soluçãoProblema de otimização Este método sempre considera a estratégia para alcançar o resultado global ótimo (ou melhor) após o ótimo (ou melhor) local no estado atual. Obviamente, se for adoptada uma estratégia melhor mas não óptima (a estratégia óptima pode não existir ou não ser fácil de pensar), o resultado global obtido não pode ser óptimo.Para obter o resultado ideal, cada estratégia de etapa intermediária deve ser ótima, portanto, o método ganancioso é estritamente usado para resolvê-la.otimizar A questão requer justificação da estratégia adotada. A ideia geral da prova é usar prova por contradição e indução matemática, ou seja, assumir que a estratégia não pode levar à solução ótima, e então obter a contradição por meio de uma série de derivações para provar que a estratégia é ótima e, finalmente, use a indução matemática para garantir o ótimo global. No entanto, para uso diário, pode não ser fácil ou fácil provar rigorosamente a estratégia que vem à mente (a prova da ganância é muitas vezes mais difícil do que a própria ganância), então, de modo geral, se você pensar em uma estratégia que pareça viável, E se você não puder dar um contra-exemplo, seja corajoso o suficiente para implementá-lo.

1. Agrupe o menor número

Dado um número de números de 0 a 9, você pode organizar esses números em qualquer ordem, mas deve usá-los todos e tornar o número de destino o menor possível (é claro, 0 não pode ser o primeiro, por exemplo). dois 0, dois 1, três 5 e um 8, o menor número obtido é 100155858.

Acredito que você pode ver a estratégia imediatamente: primeiro selecione o menor número que não seja 0 de 1 a 9 para gerar e, em seguida, produza os números de 0 a 9. O número de vezes que cada número é gerado é o número restante.

Prova de estratégia correta：

  • Em primeiro lugar, como todos os números devem participar da combinação, é determinado o número de dígitos do resultado final.
  • Como o bit mais alto não é 0, escolha um número tão pequeno quanto possível como o primeiro bit - o teorema do bit mais alto
  • Os dígitos restantes também devem ser produzidos de pequeno para grande ~

O livro é muito abstrato e parece um pouco errado. Aqui o próprio blogueiro escreveu um:

  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 não é difícil, o principal é pensar com clareza~

2.Inventário Mooncake

  • Entrada: Insira N e M na primeira linha: o número de tipos de mooncake de N dígitos e a demanda de mercado de M dígitos por mooncakes N devem ser inseridos nas próximas duas linhas: os N números na primeira linha correspondem a; os tipos atuais. Quanto você pode ganhar depois de vender todos os mooncakes, e o número N na segunda linha corresponde ao número total atual de mooncakes ~
  • Produção necessária: renda máxima sob demanda especificada

Imagine se você fosse o chefe, como seria “ganancioso”? Obviamente - se você só precisasse vender o maior número possível de mooncakes com o preço unitário mais caro possível dentro da demanda limitada, não seria possível obter o maior volume de negócios? A seguinte implementação escrita pelo próprio blogueiro é diferente daquela do livro:

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

Experimente com cuidado o loop whlie acima: quando M não for 0 - ou seja, ainda há demanda, venda os mooncakes mais caros. Venda um por um em ordem: Se a demanda atual for suficiente para vender todos os tipos atuais, o preço total será adicionado diretamente, se não for suficiente para vender todos os tipos atuais, então venda tantos quantos houver; são e calculam com base no preço unitário ~

Vamos testá-lo com o caso de teste do livro:

  • 3 20
  • 18 15 10
  • 75 72 45

O resultado é 94,50, o que é consistente com a resposta padrão~

Além disso, o blogueiro aqui escreve diretamente a classificação na função principal, escreve-a em uma função independente e depois a chama. Parece haver um bug no vetor do tipo de estrutura e a classificação não é bem-sucedida. razão, você pode escrever na área de comentários ~

2. Intervalo ganancioso

A questão central é a seguinte:

Para este tipo de pergunta, você só precisa lembrar——Dê prioridade ao intervalo com o extremo esquerdo maior！

 

Vamos falar sobre por que fazemos isso, como mostra a imagem acima: não é difícil de encontrar,Para garantir o maior número possível de escolhas, quando um intervalo mais longo contém um intervalo mais curto, devemos selecionar primeiro o intervalo mais curto, Isso é fácil de entender.

Para a situação acima, como intervalos sobrepostos como 1 e 2, não é difícil descobrir que se você selecionar o intervalo 1 com o maior ponto final esquerdo, ele ocupará apenas a posição 9, enquanto se você selecionar o intervalo 2, ele ocupará posição 8. Posição - Isto obviamente não está de acordo com a ideia de gastar o mínimo de dinheiro possível (gastar menos espaço), então você deve escolher o mais à esquerda possível, para que haja mais espaços vazios à direita ~ como acima,Podemos ver pelo cálculo manual que existem no máximo 4 disjuntos.

Código do livro didático:

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

No entanto, os blogueiros ainda não gostam de arrays originais.

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

O teste é o seguinte:

 

Em geral, o método guloso é uma ideia algorítmica usada para resolver um tipo de problema de otimização e espera derivar o resultado ótimo global a partir de uma estratégia ótima local.algoritmo ganancioso Os problemas aplicáveis ​​devem satisfazer as propriedades da subestrutura ótima, ou seja, a solução ótima de um problema pode ser efetivamente construída a partir das soluções ótimas de seus subproblemas. Obviamente nem todos os problemas são adequados para o método guloso, mas isso não impede que o algoritmo guloso se torne um algoritmo simples, prático e eficiente.

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência