Probleme de informatica - enunturi si rezolvari

Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (10)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Problema rucsacului (cazul continuu)
O persoana are un rucsac cu care poate transporta o greutate maxima g. Persoana are la dispozitie n obiecte pentru care stie greutatea si castigul obtinut daca transporta obiectul.
Fiecare obiect poate fi transportat integral sau taiat.
Sa se precizeze ce obiecte alege persoana si in ce proportie le ia astfel incat castigul total sa fie maxim si sa nu se depaseasca greutatea maxima a rucsacului.
Exemplu:
g=3 n=3
obiectele(greutate,castig):
2 2
1 4
3 6
Solutie(greutate, castig, raport taiere):
1,4,1
3,6,0.6667 (al doilea obiect se ia in raport de 2/3)
castig maxim=8


#include<fstream>
#include<iomanip>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

struct obiect
{
    float g,c,r;//greutate, castig, raportul cat se ia din obiect
};

void citire(float &g, int &n, obiect a[])
{
    fin>>g>>n;
    for(int i=1;i<=n;i++)
        { fin>>a[i].g>>a[i].c;
          a[i].r=0;//initial nu se foloseste obiectul
        }
}

void ordonare(int n, obiect a[])//ordonare dupa castig/greutate
{
    int i,j;
    obiect aux;
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
            if(a[i].c/a[i].g<a[j].c/a[j].g)
            {
                aux=a[i]; a[i]=a[j]; a[j]=aux;
            }
}

void afisare(int n, obiect a[])
{
    float c=0;
    for(int i=1;i<=n;i++)
        { fout<<a[i].g<<","<<a[i].c<<","<<setprecision(4)<<a[i].r<<"\n";
          c=c+a[i].c*a[i].r;
        }
    fout<<"castig maxim="<<c;
}

void greedy(float g, int n, obiect a[])
{
    obiect s[100];
    int i,k;
    float sp=0;
    k=0; i=1;
    while(sp<g)
    {
        if(sp+a[i].g<=g)
        { sp=sp+a[i].g;
          s[++k]=a[i];
          s[k].r=1;//obiect intreg
        }
        else
        {
          s[++k]=a[i];
          s[k].r=(g-sp)/a[i].g;//obiect fractionat
          sp=g;
        }
        i++;
    }
    afisare(k,s);
}

int main()
{
    int n;
    obiect a[100];
    float g;
    citire(g,n,a);
    ordonare(n,a);
    greedy(g,n,a);
    fin.close();
    fout.close();
}

 

17 aug 2018
Site-ul conține 867 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian