Beispiel für einen gierigen C++-Algorithmus (Veranstaltungsortanordnung, Intervallauswahl).

Dies ist die erste Aufnahme nach dem Erlernen des Algorithmus-Kurses. Allmählich nehmen die Faktoren zu, die beim Programmierdesign berücksichtigt werden müssen. Diese Gleichung lässt mich zutiefst verstehen. Von der einfachen C++-Programmierung bis hin zur Auswahl geeigneter Datenstrukturen müssen wir nun einen Schritt weiter gehen und die Effizienz der Programmausführung auf der Algorithmusebene berücksichtigen. Mein Verständnis des Algorithmus besteht darin, bessere Ausführungsergebnisse mit weniger Overhead zu erzielen.

Die Divide-and-Conquer-Methode und die dynamische Programmierung wurden noch nie zuvor aufgezeichnet. Als ich den Greedy-Algorithmus lernte, hatte ich das Gefühl, dass ich zusammenfassen musste, was ich gelernt hatte könnte es besser verstehen. Der Entwurf der dynamischen Programmierung muss die optimalen Unterstruktureigenschaften und überlappenden Teilprobleme erfüllen und eine Bottom-up-Strategie anwenden, um den optimalen Wert zu berechnen und die insgesamt optimale Lösung zu finden. Dieser Vorgang ist manchmal ziemlich schwierig. Die Hauptsache besteht darin, den rekursiven Ausdruck zu schreiben und die Tabelle von unten nach oben auszufüllen. Die Greedy-Strategie ähnelt ein wenig der dynamischen Programmierung, unterscheidet sich jedoch in einigen Aspekten. Manchmal ist die Idee eines Greedy-Algorithmus einfacher. Erfüllt es die Teilproblemoptimalität und erhält es die Gesamtoptimalität? Zwei Bedingungen: optimale Unterstruktureigenschaft und gierige Auswahleigenschaft. Die Erfüllung der Eigenschaft der gierigen Auswahl muss die Eigenschaft der optimalen Unterstruktur erfüllen, während die Erfüllung der Eigenschaft der optimalen Unterstruktur nicht unbedingt die Eigenschaft der gierigen Auswahl erfüllt. Beispielsweise kann das Rucksackproblem mit einem gierigen Algorithmus gelöst werden, während das 0-1-Rucksackproblem nur gelöst werden kann mit dynamischer Programmierung gelöst werden.

Typische Aktivitätsanordnung für gierige Probleme, es gibt n Aktivitäten, die Startzeit und die Endzeit sind angegeben und es sollten so viele Aktivitäten wie möglich arrangiert werden (die Zeit steht nicht im Widerspruch zueinander). Die richtige gierige Idee zur Lösung dieses Problems besteht darin, die Endzeit jeder Aktivität als Vergleichsvariable zu verwenden, die Aktivitäten in aufsteigender Reihenfolge der Endzeit zu sortieren und dann einen Vergleich und eine Auswahl durchzuführen. Es gibt einige Unterschiede zwischen den Fragen zur Veranstaltungsortgestaltung und den Aktivitäten. Das Folgende ist mein Problemlösungsprozess.

7-2 Probleme bei der Organisation von Veranstaltungsorten (20 Punkte)

Angenommen, Sie möchten eine Reihe von Aktivitäten an genügend Veranstaltungsorten organisieren und hoffen, so wenige Veranstaltungsorte wie möglich zu nutzen. Entwerfen Sie einen effizienten Greedy-Algorithmus für die Planung. (Dieses Problem ist eigentlich das berühmte Diagrammfärbungsproblem. Wenn jede Aktivität als Scheitelpunkt des Diagramms betrachtet wird, werden inkompatible Aktivitäten durch Kanten verbunden. Die minimale Anzahl von Färbungen, die dazu führen, dass benachbarte Scheitelpunkte unterschiedliche Farben haben, entspricht dem, was gefunden wird. Minimum Anzahl der Veranstaltungsorte. )

Eingabeformat:

Die erste Zeile enthält 1 positive Ganzzahl k, was angibt, dass k Veranstaltungen organisiert werden müssen. In den nächsten k Zeilen enthält jede Zeile zwei positive ganze Zahlen, die jeweils die Startzeit und die Endzeit von k geplanten Aktivitäten darstellen. Die Zeit wird in Minuten gemessen, beginnend bei 0 Uhr.

Ausgabeformat:

Geben Sie die Mindestanzahl an Veranstaltungsorten aus.

Eingabebeispiel:

5
1 23
12 28
25 35
27 80
36 50

Ausgabebeispiel:

3

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
    int begin;
    int end;
    int flag;//标记该活动是否被安排，0表示未安排，1表示已安排 
}t[10001];
int cmp(const node &a,const node &b)//比较规则：以结束时间升序排列 
{ 
    return a.end<b.end;
 } 
int main()
{
    int i,j,n;
    node temp;
    cin>>n;
    for(i=0;i<n;i++) 
    {
        cin>>t[i].begin>>t[i].end;
        t[i].flag=0;
    }
    sort(t,t+n,cmp);
        
    int sum=0;//总共需要的会场数量 
    for(i=0;i<n;i++)//方法2 
    {
        if(!t[i].flag)//找到未安排的活动，进行场地安排 
        {
            sum++;
            int p=i;
            for(j=p+1;j<n;j++)//当前活动结束时间与下一个活动开始不相交 ，则安排到同一个会场 
            {
                if(t[p].end<=t[j].begin&&!t[j].flag)
                {
                    p=j;t[j].flag=1;
                }
            }
            t[i].flag=1;
        }
    }
    cout<<sum;
    return 0;
}

Die gierige Strategie lautet: Ordnen Sie so viele nicht widersprüchliche Aktivitäten wie möglich an einem Ort an, wenn die Aktivität die Zeit hat Bei Überschneidungen wird an einen anderen Veranstaltungsort verlegt.

Ordnen Sie alle Aktivitäten in aufsteigender Reihenfolge nach Endzeit, verwenden Sie die Sortierfunktion und passen Sie die cmp-Methode an. Im Schleifenkörper können Sie jedes Mal eine außerplanmäßige Aktivität finden und diese Aktivität verwenden, um nach anderen Aktivitäten zu suchen, die gleichzeitig an einem Veranstaltungsort durchgeführt werden können (dieser Schritt ist in der inneren Schleife nach zwei Schleifenebenen verschachtelt). , alle Aktivitäten sind arrangiert. Nun ist die erforderliche Anzahl an Veranstaltungsorten, also die Summe, berechnet.

Ein ähnliches Problem ist die Intervallpunktauswahl

7-10-Punkte-Auswahlproblem (15 Punkte)

Es gibt n geschlossene Intervalle auf der Zahlenachse [ai, bi]. Nehmen Sie so wenige Punkte wie möglich, damit es in jedem Intervall mindestens einen Punkt gibt (die Punkte in verschiedenen Intervallen können gleich sein).

Eingabeformat:

Eine Zahl n in der ersten Zeile, die angibt, dass es n geschlossene Intervalle gibt. In den folgenden n Zeilen enthält jede Zeile 2 Zahlen, die das geschlossene Intervall [ai, bi] darstellen.

Ausgabeformat:

Eine Ganzzahl, die mindestens angibt, wie viele Punkte es gibt werden benötigt

Eingabebeispiel:

Geben Sie hier eine Reihe von Eingaben an. Zum Beispiel:

3
1 3
2 4
5 6

Ausgabebeispiel:

Die entsprechende Ausgabe wird hier angegeben. Zum Beispiel: 2

Ich möchte die gemeinsamen Segmente mehrerer Intervalle herausfinden und aufzeichnen, welche Intervalle in jedem gemeinsamen Segment enthalten sind, um den minimalen Auswahlpunkt zu berechnen. Später stellte ich fest, dass diese Idee tatsächlich vereinfacht werden kann: Verwenden Sie das rechte Ende als Schallwand, um zu sehen, ob es andere Intervalle davor gibt. Andernfalls bedeutet dies, dass es keine gemeinsamen gibt Sie müssen die Schallwandposition zählen und verschieben, um mit der Suche fortzufahren. Die gierige Strategie besteht darin, den richtigen Endpunkt des Intervalls auszuwählen, um sicherzustellen, dass es ein größeres Schnittsegment enthalten kann, und die wenigsten Punkte auszuwählen.

#include<bits/stdc++.h>
using namespace std;
struct dot{
    int l,r;
    bool v[10001];
}dots[10001];
int cmp(const dot &a,const dot &b)//比较规则，按区间右端点升序排列 
{
    return a.r<b.r;
} 
int main()
{
    int n,i,j,count=1,select;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>dots[i].l>>dots[i].r;
    sort(dots,dots+n,cmp);//预处理，将区间按规则排好序，方便后续比较 
    select=dots[0].r;
    //贪心策略是选择区间右端点，保证能够包含更大交叉段，选的点最少 
    for(i=1;i<n;i++)//每次将当前选择的一个区间的右端点与下一个（或者同一区间，可忽略）左端比较 
    {
        if(dots[i].l>select)//如果没有交叉，选点+1,并以此区间右端为新一轮比较的点 
        {
            count++;
            select=dots[i].r;
        }
    }
    cout<<count;
    return 0;
}

Nachdem ich Algorithmen gelernt habe, ist es für mich sehr wichtig, die Auswahl der Algorithmen vor dem Programmieren zu ändern. Das Studium und die Erforschung typischer Algorithmen ist sehr wichtig und tiefgründig!

Dieser Artikel stammt aus der Spalte C#.Net-Tutorial , willkommen zum Lernen!

Das obige ist der detaillierte Inhalt vonBeispiel für einen gierigen C++-Algorithmus (Veranstaltungsortanordnung, Intervallauswahl).. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!