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

<syntaxhighlight lang="python"> 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

1. Citirea datelor de intrare

n, GMax = map(int, input().split()) obiecte = [tuple(map(int, input().split())) for _ in range(n)]

1. Calcularea și afișarea câștigului maxim

rezultat = castig_maxim(n, GMax, obiecte) print(rezultat) </syntaxhighlight>