Compartir tecnología

Resumen de "Notas de algoritmo" n.° 6: codicioso

2024-07-12

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

1. Codicia simple

        método codiciosoEs una especie de soluciónProblema de optimizacion Este método siempre considera la estrategia para lograr el resultado global óptimo (o mejor) después del óptimo local (o mejor) en el estado actual. Obviamente, si se adopta una estrategia mejor pero no óptima (la estrategia óptima puede no existir o no es fácil pensar en ella), el resultado global obtenido no puede ser óptimo.Para obtener el resultado óptimo, se requiere que cada estrategia de paso intermedio sea óptima, por lo que se utiliza estrictamente el método codicioso para resolver el problema.optimizar La cuestión requiere una justificación de la estrategia adoptada. La idea general de la prueba es utilizar la prueba por contradicción e inducción matemática, es decir, asumir que la estrategia no puede conducir a la solución óptima, y ​​luego obtener la contradicción mediante una serie de derivaciones para demostrar que la estrategia es óptima. Y finalmente utilizar la inducción matemática para garantizar el óptimo global. Sin embargo, para el uso diario, puede que no sea el momento o no sea fácil probar rigurosamente la estrategia que le viene a la mente (la prueba de la codicia suele ser más difícil que la codicia misma), por lo que, en términos generales, si piensa en una estrategia que parece factible, Y si no puedes dar un contraejemplo, entonces sé lo suficientemente valiente para implementarlo.

1. Agrupa el número más pequeño.

Dado un número de números del 0 al 9, puede organizar estos números en cualquier orden, pero debe usarlos todos y hacer que el número objetivo sea lo más pequeño posible (por supuesto, 0 no puede ser el primero). dos 0, dos 1, tres 5 y un 8, el número más pequeño obtenido es 100155858.

Creo que puede ver la estrategia de inmediato: primero seleccione el número más pequeño que no sea 0 del 1 al 9 para generar, y luego genere los números del 0 al 9. La cantidad de veces que se genera cada número es el número restante.

Prueba de estrategia correcta：

  • En primer lugar, dado que todos los números deben participar en la combinación, se determina el número de dígitos en el resultado final.
  • Dado que el bit más alto no es 0, elija un número lo más pequeño posible como primer bit: el teorema del bit más alto
  • Los dígitos restantes también deben mostrarse de pequeño a grande ~

El del libro de texto es realmente demasiado abstracto y parece un poco incorrecto. Aquí el propio blogger escribió uno:

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

Lógicamente no es difícil, lo principal es pensar con claridad~

2.Inventario de pastel de luna

  • Entrada: Ingrese N y M en la primera línea: el número de tipos de pasteles de luna de N dígitos y la demanda del mercado de M dígitos para pasteles de luna deben ingresarse en las dos líneas siguientes: los N números en la primera línea corresponden a; los tipos actuales ¿Cuánto puedes ganar después de vender todos los pasteles de luna? El número N en la segunda línea corresponde al número total actual de pasteles de luna ~
  • Producción requerida: ingreso máximo bajo una demanda específica

Imagínese si usted fuera el jefe, ¿cómo sería "codicioso"? Obviamente, si sólo necesita vender tantos pasteles de luna con el precio unitario más caro posible dentro de una demanda limitada, ¿no sería posible obtener la mayor facturación? La siguiente es una implementación escrita por el propio blogger, que es diferente a la del libro de texto:

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

Pruebe con cuidado el ciclo whlie de arriba: cuando M no es 0, es decir, todavía hay demanda, venda los pasteles de luna más caros. Vender uno por uno en orden: si la demanda actual es suficiente para vender todos los tipos actuales, el precio total se sumará directamente; si no es suficiente para vender todos los tipos actuales, se venderán tantos como haya; son y se calculan en función del precio unitario ~

Probémoslo con el caso de prueba del libro de texto:

  • 3 20
  • 18 15 10
  • 75 72 45

El resultado es 94,50, que es coherente con la respuesta estándar ~

Además, el blogger aquí escribe directamente la clasificación en la función principal, la escribe en una función independiente y luego la llama. Parece que hay un error en el vector de tipo de estructura y la clasificación no se realiza correctamente. motivo, puedes escribirlo en el área de comentarios ~

2. Intervalo codicioso

El tema de la pregunta es el siguiente:

Para este tipo de preguntas, sólo necesitas recordar——Dar prioridad al intervalo con el punto final izquierdo más grande！

 

Hablemos de por qué hacemos esto, como se muestra en la imagen de arriba: no es difícil de encontrar,Para garantizar tantas opciones como sea posible, cuando un intervalo más largo contiene un intervalo más corto, primero debemos seleccionar el intervalo más corto., esto es facil de entender.

Para la situación anterior, como la superposición de intervalos como 1 y 2, no es difícil encontrar que si selecciona el intervalo 1 con el extremo izquierdo más grande, solo ocupará la posición 9, mientras que si selecciona el intervalo 2, ocupará posición 8. Posición: esto obviamente no está en línea con la idea de que los codiciosos gasten la menor cantidad de dinero posible (gastando menos espacio), por lo que debes elegir lo más a la izquierda posible, para que haya más espacios vacíos. a la derecha ~ como arriba,Podemos ver mediante cálculos manuales que hay como máximo 4 disjuntos.

Código del libro de texto:

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

Sin embargo, a los bloggers todavía no les gustan las matrices originales. Aquí hay una versión de estructura vectorial:

  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 prueba es la siguiente:

 

En general, el método codicioso es una idea algorítmica que se utiliza para resolver un tipo de problema de optimización y espera derivar el resultado óptimo global a partir de una estrategia óptima local.algoritmo codicioso Los problemas aplicables deben satisfacer las propiedades de la subestructura óptima, es decir, la solución óptima de un problema puede construirse efectivamente a partir de las soluciones óptimas de sus subproblemas. Obviamente no todos los problemas son adecuados para el método codicioso, pero esto no impide que el algoritmo codicioso se convierta en un algoritmo simple, práctico y eficiente ~

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi informacion de contacto

Correo