1340 - Rucsac

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

4 30

10 60

5 50

12 60

20 140

Ieșire

220

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.

Rezolvare

def validare_date(n, GMax, obiecte):
    if not (1 <= n <= 1000):
        raise ValueError("n trebuie să fie între 1 și 1000")

    if not (1 <= GMax <= 10000):
        raise ValueError("GMax trebuie să fie între 1 și 10000")

    for greutate, valoare in obiecte:
        if not (1 <= greutate <= 10000 and 1 <= valoare <= 10000):
            raise ValueError("Greutatea și valoarea fiecărui obiect trebuie să fie între 1 și 10000")

def castig_maxim(n, GMax, obiecte):
    obiecte.sort(key=lambda x: x[1] / x[0], reverse=True)  # Sortează obiectele după raportul valoare/greutate în ordine descrescătoare

    castig_total = 0  
    greutate_actuala = 0  

    for obiect in obiecte:
        greutate, valoare = obiect
        if greutate_actuala + greutate <= GMax:
            castig_total += valoare
            greutate_actuala += greutate
        else:
            fractiune = (GMax - greutate_actuala) / greutate  # Calculăm cât din obiect putem lua pentru a umple rucsacul
            castig_total += fractiune * valoare
            break  

    return castig_total

# Citirea datelor de intrare
n, GMax = map(int, input().split())
obiecte = [tuple(map(int, input().split())) for _ in range(n)]

# Calcularea și afișarea câștigului maxim
rezultat = castig_maxim(n, GMax, obiecte)
print(rezultat)