Cod sursa(job #2782214)

Utilizator CornelProgramatorMarin Florin Eduard Marian CornelProgramator Data 11 octombrie 2021 22:05:53
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb

#include <iostream>
using namespace std;





///numar perechi,
int n;

///greutate,valoare si cost/kg  fiecare pereche
int G[1001],V[1001];
float C[1001];
///greutate maaxima
int GMax;

int main()
{
    ///citire date de intrare
    cin>>n>>GMax;

    int i;
    for(i=1; i<=n; i++)
        cin>>G[i]>>V[i];



    ///prelucrare cost/kg;
    for(i=1; i<=n; i++)
        C[i]=(V[i]*1.0)/G[i];


    ///sortare C[i] crescator, O(n^2)
    int j,aux;
    for(i=1; i<=n; i++)
        for(j=i+1; j<=n; j++)
            if(C[i]<C[j]){
                aux=C[i];
                C[i]=C[j];
                C[j]=aux;

                aux=G[i];
                G[i]=G[j];
                G[j]=aux;

                aux=V[i];
                V[i]=V[j];
                V[j]=aux;

            }
           /* cout<<"valoare: ";
             for(i=1; i<=n; i++)
            cout<<C[i]<<' ';
        cout<<endl;
         cout<<"greutate: ";
            for(i=1; i<=n; i++)
            cout<<G[i]<<' ';
        cout<<endl;
         cout<<"pret: ";
            for(i=1; i<=n; i++)
            cout<<V[i*/


    ///parcurgere C[i]
    int greutate=0,castig=0;
    i=1;
    if(G[1]>GMax)
        castig=0;
    else
    while(i<=n && greutate<GMax){

        if(G[i]+greutate>GMax)
            castig+=(GMax-greutate)*C[i], greutate=GMax+1;///furam cat mai putem
        else castig+=V[i], greutate+=G[i];
        i++;
    }

    ///afisare rezultate;
        cout<<castig;



         /*for(i=1; i<=n; i++)
            cout<<C[i]<<' ';
        cout<<endl;*/


    return 0;
}