Motxilla amb pesos i valors P27895


Statement
 

pdf   zip

html

Teniu una motxilla que aguanta fins a p unitats de pes. Donats n objectes, cadascun amb un pes pi i un valor vi, calculeu la suma màxima de valors que es pot aconseguir, de manera que la suma de pesos no passi de p. Tingueu en compte que els objectes no es poden partir en trossos: o s’agafen, o es descarten.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb p i n, seguits de n parells d’enters pi vi. Suposeu 1 ≤ p ≤ 1000, 1 ≤ n ≤ 1000, 1 ≤ pip, i 1 ≤ vi ≤ 106.

Sortida

Per a cada cas, escriviu el màxim valor dels objectes que es poden guardar a la motxilla.

Pista

Inspireu-vos en el problema d’aconseguir un cert canvi amb un conjunt de monedes donat. Fixeu-vos que els pesos són enters, i relativament petits.

Public test cases
  • Input

    10 3
    7 3000
    8 4000
    3 2000
    
    10 3
    7 3000
    8 6000
    3 2000
    
    2 4
    1 3
    1 5
    1 7
    1 7
    

    Output

    5000
    6000
    14
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++