/*
Tehnici de programare


[1] Metoda backtracking

================

[2] Metoda Greedy
    2.1 Continium Knapsack Problem - Continium case

input.dat
5 100                   numarul de obiecte greutatea + maxima a rucsacului  n G
1000 120             profit + greutate  p1 g1
500 20
400 200
1000 100
25 1                                                   pn gn

de afisat
1315


*/


#include<fstream>
using namespace std;
int G;
int n;
float O[100][3];

int read_data()
{

}

int fill_data()
{
// aplica eficienta
}

int sort_data()
{
// sortez dupa eficienta
}

float greedy()
{
/*
G greutatea rucsacului
n numarul de obiecte
O matrice cu 3 coloane ( greutate , profit , eficienta )

 pseudocod

 profit=0
 i=1  // index la obiectului curent in sirul sortat descescator dupa eficienta

 atata timp cat in rucsac se mai pot depune obiecte si sirul de obiecte este neepuizat
                                        G>=0                                  si  i<=n
   {
    daca ( G>=O[i][1] )  atunci {
                                                        profit=profit+O[i][3]
                                                        G=G-O[i][1]
                                                  }
                     altfel {
                                aux=(G*100)/O[i][1]
                                profit_aux=(O[i][3]*aux)/100;
                                profit=profit+profit_aux;
                                G=0;
                                stop
                               }
    i=i+1;
   }

intoarce profit

*/

}

int main()
{
 read_data();
 fill_data();
 sort_data();
 cout<<greedy(); // 1315
}