Exemple d'algorithme glouton C++ (disposition des lieux, sélection d'intervalles)

C'est le premier enregistrement après avoir appris le cours d'algorithme. Petit à petit, les facteurs à prendre en compte dans la conception de la programmation augmentent. Programme = structure des données + algorithme. Cette équation me fait profondément comprendre. Depuis la simple programmation C++ jusqu'à la sélection des structures de données appropriées, nous devons maintenant aller plus loin et considérer l'efficacité de l'exécution du programme au niveau de l'algorithme. Ma compréhension de l'algorithme est d'obtenir de meilleurs résultats d'exécution avec moins de frais généraux.

La méthode diviser pour mieux régner et la programmation dynamique n'ont pas été enregistrées auparavant. Lorsque j'ai appris l'algorithme glouton, j'ai senti que je devais résumer ce que j'avais appris pour pouvoir le faire. pourrais mieux le comprendre. La conception de la programmation dynamique doit satisfaire les propriétés optimales de la sous-structure et les sous-problèmes qui se chevauchent, et adopter une stratégie ascendante pour calculer la valeur optimale et trouver la solution optimale globale. Ce processus est parfois assez difficile. L'essentiel est d'écrire l'expression récursive et de remplir le tableau de bas en haut. La stratégie gloutonne s’apparente un peu à la programmation dynamique, mais elle est différente sur certains aspects. Parfois, l’idée d’un algorithme glouton est plus facile à imaginer. Satisfait-il l’optimalité du sous-problème et obtient-il l’optimalité globale ? Deux conditions : propriété de sous-structure optimale et propriété de sélection gloutonne. Satisfaire la propriété de sélection gloutonne doit satisfaire la propriété de sous-structure optimale, tandis que satisfaire la propriété de sous-structure optimale ne satisfait pas nécessairement la propriété de sélection gloutonne. Par exemple, le problème du sac à dos peut être résolu avec un algorithme glouton, tandis que le problème du sac à dos 0-1 ne peut être résolu que. être résolu avec une programmation dynamique.

Arrangement typique des activités à problèmes gourmands, il y a n activités, l'heure de début et l'heure de fin sont indiquées, et autant d'activités que possible doivent être organisées (l'heure n'est pas en conflit les unes avec les autres). La bonne idée gourmande pour résoudre ce problème est d'utiliser l'heure de fin de chaque activité comme variable de comparaison, de trier les activités par ordre croissant de l'heure de fin, puis d'effectuer une comparaison et une sélection. Il existe certaines différences entre les problèmes d'aménagement des lieux et les activités. Voici mon processus de résolution de problèmes.

7-2 Problèmes d'aménagement des lieux (20 points)

Supposons que vous souhaitiez organiser un lot d'activités dans suffisamment de lieux et espérez utiliser le moins de lieux possible. Concevez un algorithme glouton efficace pour la planification. (Ce problème est en fait le fameux problème de coloration du graphe. Si chaque activité est considérée comme un sommet du graphe, les activités incompatibles sont reliées par des arêtes. Le nombre minimum de colorations qui font que les sommets adjacents ont des couleurs différentes correspond à ce qui est trouvé. Minimum nombre de lieux. )

Format de saisie :

La première ligne contient 1 entier positif k, indiquant qu'il y a k événements à organiser. Dans les k lignes suivantes, chaque ligne comporte 2 entiers positifs, représentant respectivement l'heure de début et l'heure de fin des k activités à planifier. Le temps est mesuré en minutes à partir de 0 heures.

Format de sortie :

Sortie du nombre minimum de lieux.

Échantillon d'entrée :

5
1 23
12 28
25 35
27 80
36 50

Échantillon de sortie :

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

La stratégie gourmande est la suivante : organiser autant d'activités non conflictuelles que possible dans un seul lieu si l'activité est le temps. chevauchements, il sera arrangé à un autre lieu.

Organisez toutes les activités par ordre croissant par heure de fin, utilisez la fonction de tri et personnalisez la méthode cmp. Dans le corps de la boucle, vous pouvez rechercher à chaque fois une activité non programmée et utiliser cette activité pour rechercher d'autres activités pouvant être hébergées dans un lieu en même temps (cette étape est imbriquée dans la boucle interne après deux couches de boucles). , toutes les activités sont organisées. D'accord, maintenant le nombre de lieux requis, la somme, a été calculé.

Un problème similaire est la sélection de points d'intervalle

Problème de sélection de 7 à 10 points (15 points)

Il y a n intervalles fermés sur l'axe des nombres [ai, bi]. Prenez le moins de points possible pour qu'il y ait au moins un point dans chaque intervalle (les points dans différents intervalles peuvent être les mêmes).

Format de saisie :

Un nombre n dans la première ligne, indiquant qu'il y a n intervalles fermés. Les n lignes suivantes, chaque ligne contient 2 nombres, représentant l'intervalle fermé [ai, bi]

Format de sortie :

Un entier, indiquant au moins combien de points sont nécessaires

Échantillon d'entrée :

Donnez un ensemble d'entrées ici. Par exemple :

3
1 3
2 4
5 6

Échantillon de sortie :

La sortie correspondante est donnée ici. Par exemple : 2

Je souhaite connaître les segments communs de plusieurs intervalles et enregistrer quels intervalles sont inclus dans chaque segment commun, afin de calculer le point de sélection minimum. Plus tard, j'ai découvert que cette idée pouvait en fait être simplifiée. La stratégie est la suivante : utilisez l'extrémité droite comme déflecteur pour voir s'il y a d'autres intervalles devant. Si c'est le cas, ne comptez pas, sinon cela signifie qu'il n'y a pas de commun. segments. Vous devez compter et déplacer la position du déflecteur pour continuer la recherche. La stratégie gourmande consiste à sélectionner le bon point d'extrémité de l'intervalle pour s'assurer qu'il peut contenir un segment d'intersection plus grand et sélectionner le moins de points.

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

Après avoir appris les algorithmes, j'ai découvert que la résolution de problèmes nécessite un changement de réflexion avant la programmation. Nous devons également apprendre des grands. L'étude et la recherche d'algorithmes typiques sont très vastes. et profond !

Cet article provient de la rubrique Tutoriel C#.Net , bienvenue pour apprendre !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!