ID #123 · Colecția InfoAs · Operatori și expresii

Problema Rucsac 2

## Cerință Se dă un set de `n` tipuri de obiecte, pentru fiecare cunoscându-se greutatea și valoarea sa. Există o infinitate de obiecte de fiecare tip. Să se găsească un grup de obiecte pentru care suma valorilor lor să fie maximă, iar greutatea totală a lor să nu depășească o valoare setată `gmax`. În grup pot face parte oricare tip de obiecte. ## Date de intrare Programul citește de la tastatură, de pe prima linie, numerele naturale `n` și `gmax`, separate printr-un spațiu, iar de pe următoarele `n` linii, câte o pereche de valori separate printr-un spațiu ce reprezintă greutatea și valoarea fiecărui obiect în parte. ## Date de ieșire Programul afișează pe ecran un singur număr natural ce reprezintă suma maximă care se poate obține alegând un grup de obiecte ale căror greutate adunată nu depășește `gmax`. ## Restricții și precizări * `1 ≤ n, gmax ≤ 1000` * `1 ≤ greutatea și valoarea fiecărui obiect în parte ≤ 1000` * Nu se pot selecta părți fracționare din obiecte