RSS

Metoda Greedy – problema rucsacului

15 Jan

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

 

3 responses to “Metoda Greedy – problema rucsacului

  1. adrei

    15/02/2011 at 14:39

    are erori problema cin o dai la executat nu merge

     
  2. Mihai Chelariu

    16/02/2011 at 16:55

    1. Problema este facuta pentru MinGW. Pentru BorlandC foloseste fstream.h si scoate using namespace std.
    2. 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!

     
  3. Iulia

    02/06/2011 at 15:46

    Problema furnizeaza un optim local, nu global:)
    Daca 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.

     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 1,459 other followers

%d bloggers like this: