Обмен технологиями

«Примечания к алгоритму» Резюме № 6 — Жадный

2024-07-12

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

1. Простая жадность

        жадный методЭто своего рода решениеПроблема оптимизации Этот метод всегда рассматривает стратегию достижения оптимального (или лучшего) глобального результата после локального оптимального (или лучшего) в текущем состоянии. Очевидно, что если будет принята лучшая, но не оптимальная стратегия (оптимальная стратегия может не существовать или ее нелегко придумать), полученный глобальный результат не может быть оптимальным.Для получения оптимального результата каждая стратегия промежуточного шага должна быть оптимальной, поэтому для решения задачи строго используется жадный метод.оптимизировать Вопрос требует обоснования принятой стратегии. Общая идея доказательства состоит в том, чтобы использовать доказательство от противного и математическую индукцию, то есть предположить, что стратегия не может привести к оптимальному решению, а затем получить противоречие посредством ряда выводов, чтобы доказать, что стратегия оптимальна. и, наконец, использовать математическую индукцию, чтобы обеспечить глобальный оптимум. Однако для повседневного использования может оказаться невозможным и непростым строго доказать стратегию, которая приходит на ум (доказательство жадности часто сложнее, чем сама жадность), поэтому, вообще говоря, если вы думаете о стратегии, которая кажется осуществимой, А если вы не можете привести контрпример, то наберитесь смелости его реализовать.

1. Сгруппируйте наименьшее число

Учитывая количество чисел от 0 до 9, вы можете расположить эти числа в любом порядке, но вы должны использовать их все и сделать целевое число как можно меньшим (конечно, 0 не может быть первым). два 0, две 1, три 5 и An 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 чисел в первой строке соответствуют текущие типы. Сколько вы сможете заработать после продажи всех лунных пирожных, а число 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. }

Внимательно посмотрите на цикл выше: когда M не равно 0 — то есть спрос все еще есть, продавайте самые дорогие лунные пирожные. Продавайте по одному по порядку: Если текущего спроса достаточно, чтобы распродать все текущие типы, общая цена будет добавлена ​​напрямую, если недостаточно, чтобы распродать все текущие типы, то продайте столько, сколько есть; являются и рассчитываются на основе цены за единицу ~

Проверим это на тестовом примере из учебника:

  • 3 20
  • 18 15 10
  • 75 72 45

Результат — 94,50, что соответствует стандартному ответу~

Кроме того, блоггер здесь напрямую записывает сортировку в основную функцию, записывает ее в независимую функцию и затем вызывает ее. Похоже, в векторе типа структуры есть ошибка, и сортировка не удалась, если вы знаете. причина, вы можете написать это в комментариях~

2. Интервальная жадность

Суть вопроса следующая:

Для такого типа вопросов вам просто нужно запомнить:Отдайте приоритет интервалу с большей левой конечной точкой.！

 

Давайте поговорим о том, почему мы это делаем, как показано на картинке выше: найти не сложно,Чтобы обеспечить как можно больше вариантов выбора, когда более длинный интервал содержит более короткий интервал, мы должны сначала выбрать самый короткий интервал., это легко понять.

В приведенной выше ситуации, например, при перекрывающихся интервалах, таких как 1 и 2, нетрудно обнаружить, что если вы выберете интервал 1 с наибольшей левой конечной точкой, он займет только позицию 9, а если вы выберете интервал 2, он займет позиция 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. }

Тест заключается в следующем:

 

В общем, жадный метод — это алгоритмическая идея, используемая для решения определенного типа задач оптимизации и позволяющая получить глобальный оптимальный результат из локальной оптимальной стратегии.жадный алгоритм Применимые проблемы должны удовлетворять свойствам оптимальной подструктуры, то есть оптимальное решение проблемы может быть эффективно построено из оптимальных решений ее подзадач. Очевидно, что не все задачи подходят для жадного метода, но это не мешает жадному алгоритму стать простым, практичным и эффективным алгоритмом~

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта