Cod sursa(job #2682877)

Utilizator Florian11232Florian Susai Florian11232 Data 9 decembrie 2020 20:13:36
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define dim  6000005
using namespace std;

struct rucsac
{
    int greutate;
    int profit;
};
rucsac elem[10001];

bool cmp(rucsac e1, rucsac e2) {
    return (float) e1.profit/e1.greutate > (float) e2.profit/e2.greutate;
}

int main()
{
    freopen("rucsacfr.in", "r", stdin);
    freopen("rucsacfr.out", "w", stdout);

    int numar,capacitate,i;
    
    cin>>numar>>capacitate;
    
    for(i=0;i<numar;i++)
    {
        cin>>elem[i].greutate>>elem[i].profit;
    }

    sort(elem, elem + numar, cmp);

    /*for (i = 0; i < numar; i++) {
        out << elem[i].greutate << " " << elem[i].profit << '\n';
    }*/
    int maxi=0, idx = 0;
    float rezultat=0; 
    while(capacitate != maxi)
    {
        if (elem[idx].greutate + maxi <= capacitate) {
            // iau tot obiectul
            rezultat += elem[idx].profit;
            maxi += elem[idx].greutate;
        } else {
            // trebuie sa iau o fractiune din obiectul curent
            rezultat += (capacitate - maxi) * (float)elem[idx].profit/elem[idx].greutate; 
            maxi = capacitate;
        }
        idx++;
        // cout << rezultat << "\n";
    }

    cout<<rezultat;
    
    return 0;
}