„Algorithm Notes“ Zusammenfassung Nr. 6

„Algorithmus-Notizen“ Zusammenfassung Nr. 6 – Greedy

2024-07-12

1. Einfache Gier

gierige MethodeEs ist eine Art LösungOptimierungsproblem Diese Methode berücksichtigt immer die Strategie, das optimale (oder bessere) globale Ergebnis nach dem lokalen Optimalen (oder besseren) im aktuellen Zustand zu erzielen. Wenn eine bessere, aber nicht optimale Strategie übernommen wird (die optimale Strategie existiert möglicherweise nicht oder ist nicht leicht vorstellbar), kann das erzielte globale Ergebnis natürlich nicht optimal sein.Um das optimale Ergebnis zu erzielen, muss jede Zwischenschrittstrategie optimal sein, daher wird zur Lösung ausschließlich die Greedy-Methode verwendet.optimieren Die Frage erfordert eine Begründung der gewählten Strategie. Die allgemeine Idee des Beweises besteht darin, Beweise durch Widerspruch und mathematische Induktion zu verwenden, d. h. unter der Annahme, dass die Strategie nicht zur optimalen Lösung führen kann, und dann den Widerspruch durch eine Reihe von Ableitungen zu erhalten, um zu beweisen, dass die Strategie optimal ist und schließlich die mathematische Induktion verwenden, um das globale Optimum sicherzustellen. Für den täglichen Gebrauch ist es jedoch möglicherweise nicht zeitgemäß oder einfach, die Strategie, die einem in den Sinn kommt, rigoros zu beweisen (der Beweis der Gier ist oft schwieriger als die Gier selbst). Wenn Sie also über eine Strategie nachdenken, die machbar erscheint, Und wenn Sie kein Gegenbeispiel nennen können, dann seien Sie mutig genug, es umzusetzen.

1. Gruppieren Sie die kleinste Zahl

Bei einer gegebenen Anzahl von Zahlen von 0 bis 9 können Sie diese Zahlen in beliebiger Reihenfolge anordnen, müssen jedoch alle verwenden und die Zielzahl so klein wie möglich machen (natürlich kann 0 nicht die erste sein). zwei Nullen, zwei Einsen, drei Fünfen und eine 8, die kleinste erhaltene Zahl ist 100155858.

Ich glaube, Sie können die Strategie sofort erkennen: Wählen Sie zuerst die kleinste Zahl von 1 bis 9 aus, die nicht 0 ist, und geben Sie dann die Zahlen von 0 bis 9 aus. Die Anzahl der Ausgaben jeder Zahl ist ihre verbleibende Zahl.

Beweis der richtigen Strategie：

Da alle Zahlen an der Kombination teilnehmen müssen, wird zunächst die Anzahl der Ziffern im Endergebnis ermittelt.
Da das höchste Bit nicht 0 ist, wählen Sie als erstes Bit eine möglichst kleine Zahl – der Satz über das höchste Bit
Die restlichen Ziffern sollten ebenfalls von klein nach groß ausgegeben werden~

Das Lehrbuch ist zu abstrakt und scheint etwas falsch zu sein. Hier hat der Blogger selbst eines geschrieben:


#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];
}

Logischerweise ist es nicht schwer, die Hauptsache ist, klar zu denken~

2.Mooncake-Inventar

Eingabe: Geben Sie N und M in die erste Zeile ein: die Anzahl der N-stelligen Mooncake-Typen, und die M-stellige Marktnachfrage nach Mooncakes müssen in die nächsten beiden Zeilen eingegeben werden: Die N-Nummern in der ersten Zeile entsprechen die aktuellen Typen. Wie viel können Sie verdienen, nachdem Sie alle Mooncakes verkauft haben, und die Zahl N in der zweiten Zeile entspricht der aktuellen Gesamtzahl der Mooncakes~
Erforderlicher Output: maximales Einkommen bei spezifizierter Nachfrage

Stellen Sie sich vor, wenn Sie der Chef wären, wie würden Sie „gierig“ sein? Offensichtlich – wenn Sie innerhalb der begrenzten Nachfrage nur so viele Mooncakes zum teuersten Stückpreis wie möglich verkaufen müssten, wäre es dann nicht möglich, den meisten Umsatz zu erzielen? Die folgende vom Blogger selbst geschriebene Implementierung unterscheidet sich von der im Lehrbuch:


#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;
}

Probieren Sie die Whlie-Schleife oben sorgfältig aus: Wenn M nicht 0 ist, das heißt, es besteht immer noch Nachfrage, verkaufen Sie die teuersten Mondkuchen. Verkaufen Sie einen nach dem anderen: Wenn die aktuelle Nachfrage ausreicht, um alle aktuellen Typen zu verkaufen, wird der Gesamtpreis direkt addiert; wenn es nicht ausreicht, um alle aktuellen Typen zu verkaufen, dann verkaufen Sie so viele wie vorhanden sind und berechnen basierend auf dem Stückpreis~

Testen wir es mit dem Testfall aus dem Lehrbuch:

3 20
18 15 10
75 72 45

Das Ergebnis ist 94,50, was mit der Standardantwort übereinstimmt

Darüber hinaus schreibt der Blogger die Sortierung direkt in die Hauptfunktion, schreibt sie dann in eine unabhängige Funktion und ruft sie dann auf. Es scheint einen Fehler im Strukturtypvektor zu geben, und die Sortierung ist nicht erfolgreich Grund, du kannst es in den Kommentarbereich schreiben~

2. Intervall gierig

Der Fragenstamm lautet wie folgt:

Bei dieser Art von Frage müssen Sie sich nur daran erinnern:Geben Sie dem Intervall mit dem größeren linken Endpunkt Priorität！

Lassen Sie uns darüber sprechen, warum wir das tun, wie im Bild oben gezeigt: Es ist nicht schwer zu finden,Um möglichst viele Auswahlmöglichkeiten zu gewährleisten, müssen wir, wenn ein längeres Intervall ein kürzeres Intervall enthält, zuerst das kürzeste Intervall auswählen, das ist leicht zu verstehen.

In der oben genannten Situation, beispielsweise bei überlappenden Intervallen wie 1 und 2, ist es nicht schwer festzustellen, dass bei Auswahl des Intervalls 1 mit dem größten linken Endpunkt nur Position 9 belegt wird, während bei Auswahl von Intervall 2 dieses nur Position 9 einnimmt Position 8. Position – Dies steht offensichtlich nicht im Einklang mit der Idee, möglichst wenig Geld auszugeben (weniger Platz auszugeben). Sie sollten daher so weit links wie möglich wählen, damit mehr Leerräume entstehen rechts ~ wie oben,Durch Handberechnung können wir sehen, dass es höchstens 4 disjunkte gibt.

Code aus dem Lehrbuch:


#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;
}

Allerdings mögen Blogger immer noch keine Original-Arrays. Hier ist eine Version mit Vektorstruktur:


#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;
}

Der Test läuft wie folgt ab:

Im Allgemeinen ist die Greedy-Methode eine algorithmische Idee, die zur Lösung einer Art Optimierungsproblem verwendet wird und darauf abzielt, das globale optimale Ergebnis aus einer lokalen optimalen Strategie abzuleiten.Gieriger Algorithmus Anwendbare Probleme müssen die Eigenschaften einer optimalen Unterstruktur erfüllen, das heißt, die optimale Lösung eines Problems kann effektiv aus den optimalen Lösungen seiner Unterprobleme konstruiert werden. Offensichtlich sind nicht alle Probleme für die Greedy-Methode geeignet, aber das hindert den Greedy-Algorithmus nicht daran, ein einfacher, praktischer und effizienter Algorithmus zu werden

Technologieaustausch

„Algorithmus-Notizen“ Zusammenfassung Nr. 6 – Greedy

1. Einfache Gier

1. Gruppieren Sie die kleinste Zahl

2.Mooncake-Inventar

2. Intervall gierig

Persönliches Profil

meine Kontaktdaten