greedy11

#include <iostream>
#include <fstream>
/**
Adott egy hátizsák, amely legtöbb m súlyt bír el és n tárgy melyeknek ismerjük a súlyát és az értékét.
 Csomagoljuk be a hátizsákot úgy, hogy az érték maximális legyen.
Pl: legyen m=40, n=6, súly=(20, 10, 4, 3, 6, 16) és érték=(60, 35, 4, 9, 12, 44)
Ha rendezzük érték szerint:
érték=(60, 44, 35, 12, 9, 4)
súly=(20, 16, 10, 6, 3, 4)
Megoldás: 20+16+3=39 és 60+44+9=113

Jobb megoldást kaphatunk, ha érték/súly szerint rendezzük:
	érték/súly=(3.5, 3, 3, 2.75, 2, 1)
érték=(35, 60, 9, 44, 12, 4)
súly=(10, 20, 3, 16, 6, 4)
Megoldás: 10+20+3+6=39 és 35+60+9+12=116
*/

using namespace std;
struct targy
{
    float s,e;

}a[50];
void beolvas(targy a[], int &n, int &m)
{
    ifstream f("hatizsak.be");
    f>>m>>n;
    for(int i=1;i<=n;i++)
        f>>a[i].s>>a[i].e;
    f.close();
}
void rendez (targy a[],int n)
{
    int jo=1;
    int nn=n;
    do{
        jo=1;
        for(int i=1;i<=nn-1;i++)
        if(a[i].e/a[i].s<a[i+1].e/a[i+1].s)
        {
            targy x=a[i];
            a[i]=a[i+1];
            a[i+1]=x;
            jo=0;
        }
        nn--;
    }while(jo==0);
}
void moho(targy a[],int n,int m)
{
    int i=1,os=0,oe=0;
    while(i<=n && m>0)
    {
        if(a[i].s<=m)
        {
            cout<<a[i].s<<" "<<a[i].e<<endl;
            os=os+a[i].s;
            oe=oe+a[i].e;
            m=m-a[i].s;
        }
        i++;
    }
    if(m>0) cout<<"A zsakban meg marad: "<<m<<endl;
    else cout<<"A zsak megtelt!"<<endl;
    cout<<oe<<" ertek van a zsakban!"<<endl;
    cout<<os<<" suly van a zsakban!"<<endl;

}
int main()
{    int n,m;
    beolvas(a,n,m);
    rendez(a,n);
    moho(a,n,m);


    return 0;
}