1063 - Arme

Cerința

Într-un joc video, un jucător trebuie să colecteze arme de diferite tipuri pentru a-și îmbunătăți arsenalul. Fiecare tip de armă are o anumită valoare, iar jucătorul dorește să maximizeze suma valorilor armelor colectate, respectând o limită de greutate pe care o poate transporta. Sarcina ta este să implementezi un program care să determine setul optim de arme pe care jucătorul le poate colecta pentru a maximiza valoarea totală, utilizând o metodă greedy.

Date de intrare

Programul citește de la tastatură:

Un număr întreg n reprezentând numărul de tipuri de arme. O listă de n perechi de numere întregi, fiecare pereche reprezentând greutatea și valoarea unei arme. Un număr întreg W reprezentând limita de greutate pe care jucătorul o poate transporta.

Date de ieșire

Pe ecran se va afișa valoarea totală maximă a armelor pe care jucătorul le poate colecta, respectând limita de greutate.

Restricții și precizări

1 ⩽ n ⩽ 100
1 ⩽ w ⩽ 1000
Greutatea și valoarea fiecărei arme sunt numere întregi pozitive

Exemplu 1

Intrare

4
2 3
3 4
4 5
5 6
5

Iesire

7

Exemplu 2

Intrare

3
1 1
3 4
4 5
5

Iesire

6

Rezolvare

<syntaxhighlight lang="python" line> def citeste_date():

   try:
       n = int(input("Introduceți numărul de tipuri de arme (n): "))
       arme = []
       for _ in range(n):
           greutate, valoare = map(int, input().strip().split())
           arme.append((greutate, valoare))
       W = int(input("Introduceți limita de greutate (W): "))
       return n, arme, W
   except ValueError:
       return None, None, None

def valideaza_date(n, arme, W):

   if not (1 <= n <= 100):
       return False
   if not (1 <= W <= 1000):
       return False
   if not all(isinstance(greutate, int) and isinstance(valoare, int) and greutate > 0 and valoare > 0 for greutate, valoare in arme):
       return False
   return True

def calculeaza_valoare_maxima(n, arme, W):

   arme.sort(key=lambda x: x[1]/x[0], reverse=True)
   greutate_totala = 0
   valoare_totala = 0

   for greutate, valoare in arme:
       if greutate_totala + greutate <= W:
           greutate_totala += greutate
           valoare_totala += valoare
       else:
           break

   return valoare_totala

def main():

   n, arme, W = citeste_date()
   
   if n is None or arme is None or W is None or not valideaza_date(n, arme, W):
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return
   
   print("Datele de intrare corespund restricțiilor impuse.")
   valoare_maxima = calculeaza_valoare_maxima(n, arme, W)
   print(valoare_maxima)

if __name__ == "__main__":

   main()

</syntaxhighlight>