11/1 - Metoda Greedy

1. La un cabinet stomatologic se prezintă simultan n pacienţi. Să se determine ordinea în care medicul stomatolog va trata pacienţii astfel încât să se minimizeze timpul mediu de aşteptare dacă se cunosc duratele tratamentelor celor n pacienţi.
ex: n=3 şi t1=60, t2=10, t3=30
Pentru ordinea 1,2,3 tm=130/3, în timp ce pentru ordinea 2,3,1 tm=50/3 (timpul minim)

#include<iostream>
using namespace std;
int main()
{int n,a[100],i,j,b[100],t=0;
cout<<"n=";
cin>>n;
for(i=1;i<=n;i++)
    {cout<<i<<".";cin>>a[i];}
for(i=1;i<=n;i++)
    b[i]=a[i];
for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
        if(b[i]>b[j])
            swap(b[i],b[j]);
cout<<"Ordinea optima"<<endl;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(b[i]==a[j])
            {cout<<j<<".";
            cout<<b[i]<<endl;}
for(i=1;i<=n;i++)
    t=t+b[i]*(n-i);
cout<<"Timp de asteptare optimizat"<<endl;
cout<<(double)t/n;
}

2. Problema spectacolelor: Într-o sală trebuie repartizate cât mai multe spectacole. Pentru fiecare se cunoaşte ora de început şi ora de sfârşit. Spectacolele nu se pot suprapune. Să se găsească numărul maxim de spectacole şi un exemplu de repartizare a acestora.

#include<iostream>
#include<fstream>
using namespace std;
struct spectacol{
    int in,sf;
}x[100];

int main()
{int n,i,j,p,k=0;
ifstream f("dlm");
f>>n;
for(i=1;i<=n;i++)
    {f>>x[i].in;
     f>>x[i].sf;}
for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
        if(x[i].sf>x[j].sf)
            swap(x[i],x[j]);
cout<<"Ordinea optima"<<endl;
p=x[1].sf;
for(i=2;i<=n;i++)
    if(x[i].in<p)
        {x[i].in=0;
         x[i].sf=0;}
    else p=x[i].sf;
for(i=1;i<=n;i++)
    if(x[i].in!=0 && x[i].sf!=0)
        {cout<<"["<<x[i].in<<","<<x[i].sf<<"]"<<endl;
        k++;}
cout<<k<<" spectacole";
}

Fişier text

10
1 5
2 6
1 10
2 3
4 8
5 7
4 9
3 4
10 11
7 9