Motxilla amb pesos i valors P27895


Statement
 

pdf   zip

thehtml

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 ≤ pi ≤ p, i 1 ≤ vi ≤ 106.

Sortida

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

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
    Other languages
    English
    Official solutions
    C++ Python Python
    User solutions
    C++