11/30 - Greedy clasa11info

Probleme

6. Se consideră un număr nelimitat de rucsaci de acelaşi tip, cu fiecare putându-se transporta o greutate maximă G şi n<=1000 obiecte de greutăţi g1, g2, …, gn. Să se determine numărul minim de rucsaci necesari pentru a transporta toate obiectele.

#include<iostream>
#include<fstream>
using namespace std;
int a[100],n,G;
void citire()
{int i;
ifstream f("date.in");
f>>n;
for(i=1;i<=n;i++)
    f>>a[i];
f>>G;
}

int main()
{int s=0,nr=1,i,j;
citire();
sort(a,n+a);
for(i=1;i<=n;i++)
    if(a[i]>G)
        a[i]=0;
for(i=n;i>0;i--)
{if(a[i]!=0)
    {s=a[i];
    cout<<a[i]<<" ";
    a[i]=0;
for(j=1;j<i;j++)
{    if(a[j]!=0)
    {    if(s+a[j]<=G)
        {    s=s+a[j];
            cout<<a[j]<<" ";
            a[j]=0;
        }
        else if(s+a[j]>G)
        {    nr++;
            s=0;
            cout<<endl;
            j=i;
        }
    }
}
    }
}
cout<<endl<<endl<<nr<<" ruxa";
}

Fişier

8
1 3 4 5 8 6 2 6
8

7. Se dau două şiruri de lungime N şi un număr K (N<1000 şi K<1000). Cele două şiruri au doar elementele 1 şi –1. Scopul este de a transforma primul şir în al doilea. Singura operaţie permisă este de a selecta o secvenţă de K elemente alăturate şi să le inversăm semnul la toate numerele cuprinse în această zonă. Dacă este posibil, se va afişa numărul minim de operaţii şi apoi poziţia de început a fiecărei operaţii efectuate.

#include<iostream>
#include<fstream>
using namespace std;
int n,k,v[10],a[10],b[10];

void citire()
{ifstream f("date.in");
int i;
f>>n>>k;
for(i=1;i<=n;i++)
    f>>a[i];
for(i=1;i<=n;i++)
    f>>b[i];
}

int verifica()
{int ok=1,i;
for(i=1;i<=n;i++)
    if(a[i]!=b[i])
        ok=0;
return ok;
}

void aplica(int i)
{int j;
for(j=i;j<i+k;j++)
    a[j]=-a[j];
}

int main()
{int i,j,k=0;
citire();
for(i=1;i<=n;i++)
    if(a[i]!=b[i])
    {aplica(i);
    v[k]=i;
    k++;
    if(verifica()==1)
        i=n+1;
    else i=1;
    }
cout<<k<<" operatii"<<endl;
for(i=0;i<k;i++)
    cout<<v[i]<<" ";
}

Fişier

5
2
-1 1 1 1 -1
1 1 -1 1 -1