#include <fstream>
using namespace std;
ifstream fin ("date.in");
ofstream fout("date.out");
int main ()
{//declarare
int pret[10], vol[10],i,n,sac,vfurt=0,aux, sch;
//citire
fin>>sac;
fin>>n;
for(i=0;i<n;i++)
fin>>vol[i]>>pret[i];
//GREEDY
//faza 1: hotul ordoneaza obiectele descrescator, dupa raportul pret/volum
do{
sch=0;
for(i=0;i<n-1;i++)
it (pret[i]/vol[i]<pret[i+1]/vol[i+1])
{sch=1;
aux=pret[i];pret[i]=pret[i+1];pret[i+1]=aux;
aux=vol[i];vol[i]=vol[i+1];vol[i+1]=aux;
}
} while (sch);
//faza 2: hotul pune obiectele in sac
for(i=0;i<n && sac>0;i++)
if (sac>=vol[i])
{sac=sac-vol[i];
vfurt=vfurt+pret[i];
}
//afisare
fout<<endl<<"In sac a ramas "<<sac<<" spatiu."<<endl<<"Valoarea furtului este "<<vfurt;
return 1;
}
are erori problema cin o dai la executat nu merge
RăspundețiȘtergere1. Problema este facuta pentru MinGW. Pentru BorlandC foloseste fstream.h si scoate using namespace std.
RăspundețiȘtergere2. implementarea umple sacul cu obiecte intregi, nu luate procentual
3. implementarea nu accepta ca volumul sacului sa fie depasit (volumul obiectelor furate <=capacitate sac).
Succes!
Problema furnizeaza un optim local, nu global:)
RăspundețiȘtergereDaca avem datele de intrare:
21
3
12 36
11 22
10 20
hotul nostru cara mai putin, dar nu obtine profitul maxim
metoda greedy e optima in cazul in care hotul poate lua bucati de obiecte.