Problem ranca

Vreme	Memorija	Ulaz	Izlaz
1 s	64 MB	stdin	stdout

Vreme

Memorija

Ulaz

Izlaz

1 s

64 MB

stdin

stdout

Jedan od najpoznatijih DP problema. Stanje zavisi od dve stvari: koje predmete smo razmotrili i koliko je kapaciteta ostalo.

Lopov je provalio u magacin noseći ranac koji može da izdrži najviše $W$ kilograma. U magacinu se nalazi $n$ predmeta, svaki sa svojom težinom i vrednošću. Svaki predmet može se uzeti najviše jednom, a predmeti se ne mogu deliti.

Odredi najveću ukupnu vrednost predmeta koje lopov može da iznese, tako da njihova ukupna težina ne pređe $W$ .

Ulaz

U prvom redu nalaze se dva broja: $n$ i $W$ , broj predmeta i kapacitet ranca.
U narednih $n$ redova nalaze se po dva broja: $w_{i}$ i $v_{i}$ , težina i vrednost $i$ -tog predmeta.

Izlaz

Jedan broj - najveća ukupna vrednost koja staje u ranac.

Primer

Input

Output

Lopov uzima treći i četvrti predmet: ukupna težina $1 + 3 = 4 \leq 5$ , ukupna vrednost $3 + 4 = 7$ .

Ograničenja

$1 \leq n \leq 100$
$1 \leq W \leq 1 0^{4}$
$1 \leq w_{i} \leq W$
$1 \leq v_{i} \leq 1 0^{6}$

Vreme	Memorija	Ulaz	Izlaz
1 s	64 MB	stdin	stdout

Odredi najveću ukupnu vrednost predmeta koje lopov može da iznese, tako da njihova ukupna težina ne pređe $W$ .

Ulaz

U prvom redu nalaze se dva broja: $n$ i $W$ , broj predmeta i kapacitet ranca.
U narednih $n$ redova nalaze se po dva broja: $w_{i}$ i $v_{i}$ , težina i vrednost $i$ -tog predmeta.

Izlaz

Jedan broj - najveća ukupna vrednost koja staje u ranac.

Primer

Input

Output

Lopov uzima treći i četvrti predmet: ukupna težina $1 + 3 = 4 \leq 5$ , ukupna vrednost $3 + 4 = 7$ .

Ograničenja

$1 \leq n \leq 100$
$1 \leq W \leq 1 0^{4}$
$1 \leq w_{i} \leq W$
$1 \leq v_{i} \leq 1 0^{6}$

Problem ranca

Ulaz

Izlaz

Primer

Ograničenja

Pošalji svoje rešenje

Problem ranca

Ulaz

Izlaz

Primer

Ograničenja

Pošalji svoje rešenje