Cerința

Într-un magazin sunt n obiecte; pentru fiecare se cunoaște greutatea G și valoarea V. Un hoț intră în magazin având un rucsac ce poate transporta o greutate maximă GMax. El va fura anumite obiecte, sau porțiuni de obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.

Să se stabilească câștigul maxim pe care îl poate obține hoțul. Câștigul este egal cu suma valorilor obiectelor furate. Câștigul adus de o fracțiune de obiect este direct proporțional cu greutatea fracțiunii.

Date de intrare

Programul citește de la tastatură numerele naturale n GMax, iar apoi n perechi de valori naturale G V, reprezentând greutatea, respectiv valoarea fiecărui obiect.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând câștigul maxim pe care îl poate obține hoțul.

Restricții și precizări

1 ≤ n ≤ 1000;
1 ≤ GMax, G, V ≤ 10000;
rezultatul va fi punctat dacă diferența dintre cel afișat de program și cel corect este mai mică decât 0.01.

Exemplu

Intrare

Ieșire

Explicație

Hoțul va lua obiectele 2 și 4 în întregime și jumătate din obiectul 1, obținând un câștig de 220.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Rucsac:

#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
#define NN 1005

struct obiect{
    int greutate, valoare;
};

int n, Gmax;
obiect O[NN];

bool fcmp(obiect A, obiect B)
{
    return A.valoare * B.greutate > A.greutate * B.valoare;
}

int main(){
    assert(cin >> n >> Gmax );
    for(int i=1 ; i<=n ; ++i)
        assert(cin >> O[i].greutate >> O[i].valoare);
    sort (O + 1 , O + n + 1, fcmp);
    int G = 0;
    double V = 0;
    int i = 1;
    while( i <= n)
    {
        if(G + O[i].greutate <= Gmax)
        {
            G += O[i].greutate;
            V += O[i].valoare;
            i ++;
        }
        else
            if(Gmax - G > 0)
            {
                int x = Gmax - G;
                double factor = 1.0 * x / O[i].greutate;
                G = Gmax;
                V += factor * O[i].valoare;
                i++;
            }
            else
                i = n + 1;
    }
    cout << V;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1340 Rucsac

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1340 Rucsac de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1340 Rucsac