Metoda GREEDY

METODA GREEDY

Este o metodă de optimizare . Se pleacă de la o problemă : Se dau un sac de capacitate C si n obiecte de capacități și prețuri diferite c1,...,cn și p1.....pn .

Fiecare obiect are prețul pi și capacitatea ci .

Se cere să se umple sacul cu o valoare cât mai mare .

Logic se vor ordona întâi descrescător rapoartele pi/ci. (sau crescător inversele acestor fracții , adică ci/pi ).

Se adună capacitățiile obiectelor  la o sumă care în final nu depășește C – capacitatea sacului .

E firesc că în sac se prea poate să nu intre toate obiectele .

Important e ca valoarea totală a acestora să fie cât mai mare.

∑ci<=C

#include<conio.h>

#include<stdio.h>

#include<iostream.h>

#pragma hdrstop;

//C-capacitate rucsac c1..cn-capacitati obiecte p1..pn-preturi obiecte

//se sorteaza pi/ci prin bubllesort descrescator

//suma capacitatilor dupa sortare<C

int C,c[10],n,p[10],x,i,y,j,s=0;//s-suma capacit obiectelor

void sortare()

{

j=0;//variabila semafor

do

{

j=0;

for(i=0;i<=n-2;i++){ if(p[i]/c[i]<p[i+1]/c[i+1]) { j=1;

                                                                                                   x=c[i];

                                                                                                   c[i]=c[i+1];

                                                                                                   c[i+1]=x;

                                                                                                   y=p[i];

                                                                                                   p[i]=p[i+1];

                                                                                                   p[i+1]=y;

                                   }                                                              }

 }while(j==1);

 }//sortare

 int main()

 {clrscr();

  cout<<"dati capacit rucsac C ";cin>>C;

  cout<<"dati nr de obiecte n ";cin>>n;

 for(i=0;i<=n-1;i++){ cout<<"c["<<i<<"]=";cin>>c[i];

                                      cout<<"p["<<i<<"]=";cin>>p[i];

                                      }

 sortare();

 cout<<"pret/capacitate"<<endl;

 for(j=0;j<=n-1;j++) if(s+c[j]<=C) { s=s+c[j]  ;

                                                                     cout<<"obiect " <<c[j]<<"  "<<p[j]<<endl;

                                                                    }

                                                                     else break;

  cout<<"se introduc in sac "<<j;

  cout<<"  obiecte cu valoare pe unitatea de capacitate- maxima ";

  getch();

return 0;

  }

Pt CodeBlocks se recomandă

·         să nu folosim clrscr , getch și nici bibliotecile conio si stdio !

·         să scriem uses namespace std

·         să scriem iostream fară .h

·         compilator Mngw