"Notes d'algorithme" Résumé n°6

"Notes d'algorithme" Résumé n°6 - Gourmand

2024-07-12

1. La simple cupidité

méthode gourmandeC'est une sorte de solutionProblème d'optimisation Cette méthode considère toujours la stratégie pour obtenir le résultat global optimal (ou meilleur) après l’optimal local (ou meilleur) dans l’état actuel. Évidemment, si une stratégie meilleure mais non optimale est adoptée (la stratégie optimale peut ne pas exister ou n’est pas facile à imaginer), le résultat global obtenu ne peut pas être optimal.Pour obtenir le résultat optimal, chaque stratégie d’étape intermédiaire doit être optimale, la méthode gloutonne est donc strictement utilisée pour résoudre le problème.optimiser La question nécessite de justifier la stratégie adoptée. L'idée générale de la preuve est d'utiliser la preuve par contradiction et par induction mathématique, c'est-à-dire en supposant que la stratégie ne peut pas conduire à la solution optimale, puis d'obtenir la contradiction par une série de dérivations pour prouver que la stratégie est optimale. , et enfin utiliser l'induction mathématique pour garantir l'optimum global. Cependant, pour une utilisation quotidienne, il n'est peut-être pas temps ni facile de prouver rigoureusement la stratégie qui vous vient à l'esprit (la preuve de la cupidité est souvent plus difficile que la cupidité elle-même), donc d'une manière générale, si vous pensez à une stratégie qui semble réalisable, Et si vous ne pouvez pas donner de contre-exemple, alors soyez assez courageux pour le mettre en œuvre.

1. Regroupez le plus petit nombre

Étant donné un nombre de nombres de 0 à 9, vous pouvez disposer ces nombres dans n'importe quel ordre, mais vous devez tous les utiliser et rendre le nombre cible aussi petit que possible (bien sûr, 0 ne peut pas être le premier). Par exemple, entrez). deux 0, deux 1, trois 5 et An 8, le plus petit nombre obtenu est 100155858.

Je pense que vous pouvez voir la stratégie immédiatement : sélectionnez d'abord le plus petit nombre qui n'est pas 0 de 1 à 9 à afficher, puis affichez les nombres de 0 à 9. Le nombre de fois où chaque nombre est affiché correspond à son nombre restant.

Preuve de la bonne stratégie：

Tout d'abord, puisque tous les nombres doivent participer à la combinaison, le nombre de chiffres du résultat final est déterminé.
Puisque le bit le plus élevé n'est pas 0, choisissez un nombre aussi petit que possible comme le premier bit - théorème du bit le plus élevé
Les chiffres restants doivent également être affichés de petit à grand ~

Celui du manuel est vraiment trop abstrait et semble un peu faux. Ici, le blogueur en a écrit un lui-même :


#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;
 
int main() {	
	vector<int> V;
	for(int i=1;i<=10;i++)
	{
		int temp=0;
		cin>>temp;
		V.push_back(temp);
	}
	sort(V.begin(),V.end());  //直接排成升序 
	int flag=0;  //标记 
	for(int i=0;i<=9;i++)
		if(V[i]!=0)
		{
			int temp=V[i];
			V[i]=V[0];
			V[0]=temp;
			flag=i;//保存第一个不为0的位置 
			break;	
		}
	for(int i=flag+1;i<=9;i++)  //找更小的头，直接从flag下一位开始即可，节省时间~ 
		if(V[i]<V[0]&&V[i]!=0)
		{
			int temp=V[i];
			V[i]=V[0];
			V[0]=temp;
		}
	for(int i=0;i<=9;i++)
		cout<<V[i];
}

Logiquement ce n'est pas difficile, l'essentiel est de penser clairement~

2.Inventaire Mooncake

Entrée : saisissez N et M dans la première ligne : le nombre de types de gâteaux de lune à N chiffres et la demande du marché pour les gâteaux de lune à M chiffres doivent être saisis dans les deux lignes suivantes : les nombres N dans la première ligne correspondent à les types actuels. Combien pouvez-vous gagner après avoir vendu tous les gâteaux de lune, et le nombre N dans la deuxième ligne correspond au nombre total actuel de gâteaux de lune ~
Résultat requis : revenu maximum selon une demande spécifiée

Imaginez si vous étiez le patron, en quoi seriez-vous « gourmand » ? Évidemment, si vous aviez seulement besoin de vendre autant de gâteaux de lune au prix unitaire le plus cher que possible dans le cadre d'une demande limitée, ne serait-il pas possible de générer le plus de chiffre d'affaires ? Ce qui suit est une implémentation écrite par le blogueur lui-même, qui est différente de celle du manuel :


#include <cstdio>
#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;
 
struct mooncake{
	double num;  //总数 
	double income;  //总收入 
 	double price;   //单价，需要自己计算 
}; 
 
int main() {
	int N,M;
	cin>>N>>M;
	vector<mooncake> V;
	for(int i=1;i<=N;i++) 
	{
		mooncake temp;
		V.push_back(temp);
	}
	cout<<"请输入数量："<<endl;
	for(int i=1;i<=N;i++) 
	{
		double num=0;
		cin>>num;
		V[i-1].num=num;
	}
	cout<<"请输入总价："<<endl;
	for(int i=1;i<=N;i++) 
	{
		double income=0;
		cin>>income;
		V[i-1].income=income;
	}
	for(int i=0;i<=N-1;i++) 
		V[i].price=V[i].income/V[i].num; //计算单价
	//按单价降序排列！保证贵的尽可能多卖
	
	for(int i=0;i<=V.size()-1;i++)
	{
		for(int j=i;j<=V.size()-1;j++)    
			if(V[j].price>V[i].price)    
			{
				mooncake temp;
				temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			}
	}
	for(int i=0;i<=V.size()-1;i++)
		cout<<"单价第"<<(i+1)<<"高的值为："<<V[i].income<<" "<<V[i].price<<" "<<V[i].num<<endl;
	
	
	for(int i=0;i<=N-1;i++)
		cout<<V[i].num<<endl; 
	int j=0;  //使用的下标 
	double count=0;  //总利润 
	while(M>0)  //当还有需求量时 
	{
		double doubt=0;
		doubt=M-V[j].num; //用M减去当前类型的额总量 
		if(doubt>=0)//减了以后M还有剩余
		{
			M-=V[j].num;//当前种类全部卖出 
			count+=V[j].income;//直接总价相加 
			j++;
			cout<<V[j].num;
		}
		else if(doubt<0) //不够减这么多
		{
			count+=V[j].price*M;//剩余部分按照单价计算 
			break; 
		} 
	}
	cout<<"最高利润值为："<<count<<endl;
	return 0;
}

Goûtez attentivement la boucle whlie ci-dessus : lorsque M n'est pas 0, c'est-à-dire qu'il y a toujours une demande, vendez les gâteaux de lune les plus chers. Vendre un par un dans l'ordre : si la demande actuelle est suffisante pour vendre tous les types actuels, le prix total sera ajouté directement s'il ne suffit pas de vendre tous les types actuels, alors vendez-en autant qu'il y a ; sont et calculent en fonction du prix unitaire ~

Testons-le avec le cas de test du manuel :

3 20
18 15 10
75 72 45

Le résultat est 94,50, ce qui est conforme à la réponse standard~

De plus, le blogueur écrit ici directement le tri dans la fonction principale, l'écrit dans une fonction indépendante puis l'appelle. Il semble y avoir un bug dans le vecteur de type structure, et le tri ne réussit pas. raison, vous pouvez l'écrire dans la zone de commentaire~

2. Intervalle gourmand

La tige de la question est la suivante :

Pour ce type de question, il vous suffit de vous rappeler——Donner la priorité à l'intervalle avec le point final gauche le plus grand！

Parlons de la raison pour laquelle nous faisons cela, comme le montre l'image ci-dessus : ce n'est pas difficile à trouver,Afin d'assurer autant de choix que possible, lorsqu'un intervalle plus long contient un intervalle plus court, nous devons d'abord sélectionner l'intervalle le plus court., c'est facile à comprendre.

Pour la situation ci-dessus, comme les intervalles qui se chevauchent tels que 1 et 2, il n'est pas difficile de constater que si vous sélectionnez l'intervalle 1 avec l'extrémité gauche la plus grande, il n'occupera que la position 9, tandis que si vous sélectionnez l'intervalle 2, il occupera position 8. Position - Ceci n'est évidemment pas conforme à l'idée de dépenser le moins d'argent possible (dépenser moins d'espace), vous devez donc choisir le plus à gauche possible, afin qu'il y ait plus d'espaces vides à droite ~ comme ci-dessus,On peut voir par calcul manuel qu'il y en a au maximum 4 disjoints.

Code du manuel :


#include <cstdio>
#include <algorithm>
using namespace std;
 
const int maxn=110;
struct Inteval{
	int x,y;  //开区间左右端点 
}I[maxn]; 
 
bool cmp(Inteval a,Inteval b)
{
	if(a.x!=b.x)
		return a.x>b.x;   //左端点从大到小排序 
	else
		return a.y<b.y;   //左端点相同的按右端点从小到大排序 
}
 
int main() {
	int n;
	while(scanf("%d",&n,n!=0))
	{
		for(int i=0;i<n;i++)
			scanf("%d%d",&I[i].x,&I[i].y);
		sort(I,I+n,cmp); //排序区间 
		int ans=1,lastX=I[0].x;
		//ans记录总数，lastX记录上一个被选择的区间的左端点 
		for(int i=1;i<n;i++)
		{
			if(I[i].y<=lastX)   //如果该区间右端点在lastX左边 
			{
				lastX=I[i].x;  //以I[i]作为新选中的区间 
				ans++;   //不相交的区间个数+1 
			}	
		}
		printf("%dn",ans);	
	} 
	return 0;
}

Cependant, les blogueurs n’aiment toujours pas les tableaux originaux. Voici une version à structure vectorielle :


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct section{
	int x=0;
	int y=0;
	//x和y分别为左右端点 
}; 
 
 
int main() {
	int n=0;
	vector<section> V;
	cin>>n;
	for(int i=1;i<=n;i++) //读入数据 
	{
		section temp;
		int x=0,y=0;
		cin>>x>>y;
		if(x>y)   //防止左端点大于右端点 
		{
			int temp1=x;
			x=y;
			y=temp1;	
		}
		else if(x==y) //若左右端点相同 
		{
			i-=1;  //则当前输入 不算
			cout<<"不可以输入相同的左右端点！"<<endl; 
			continue;  //舍弃数据，本次循环作废~ 
		}	
		temp.x=x;
		temp.y=y;
		V.push_back(temp);
	}
	//按要求排序区间优先级 
	for(int i=0;i<=V.size()-1;i++)
	{
		for(int j=i+1;j<=V.size()-1;j++)
		{
			if(V[j].x>V[i].x)  //左端点越大越靠前
			{
				section temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			}
			else if(V[j].x==V[i].x&&V[j].y<V[i].y) //左端点相同的话，右端点小的优先 
			{
				section temp=V[j];
				V[j]=V[i];
				V[i]=temp;
			} 
		}
	}
	cout<<"顺序如下："<<endl; 
	for(int i=0;i<=V.size()-1;i++)
		cout<<V[i].x<<"~"<<V[i].y<<endl; 
	int count=1,lastX=V[0].x;
	//count用来统计总数，lastX是上一个符合条件的区间的左端点
	 
	for(int i=1;i<=V.size()-1;i++)//直接从第二个区间开始 
	{
		if(V[i].y<lastX)  //如果当前区间的右端点不和上一个左端点相加，满足题意 
		{
			lastX=V[i].x;
			count++;
		}		
	} 
	cout<<count<<endl;
	return 0;
}

Le test est le suivant :

En général, la méthode gloutonne est une idée algorithmique utilisée pour résoudre un type de problème d’optimisation et espère dériver le résultat optimal global à partir d’une stratégie optimale locale.algorithme gourmand Les problèmes applicables doivent satisfaire aux propriétés de sous-structure optimale, c'est-à-dire que la solution optimale d'un problème peut être efficacement construite à partir des solutions optimales de ses sous-problèmes. Evidemment tous les problèmes ne se prêtent pas à la méthode gloutonne, mais cela n'empêche pas l'algorithme glouton de devenir un algorithme simple, pratique et efficace~

Partage de technologie