0/1 Bel Çantası
Çətin
Dynamic ProgrammingGreedy
4000 ms
256 MB
n əşya (hər birinin çəkisi və dəyəri) və çanta tutumu capacity verilib. Hər əşyanı yalnız bir dəfə götürərək, ümumi çəki tutumu aşmadan əldə edilə biləcək maksimum dəyəri tapın.
Giriş verilənləri
Birinci sətirdə n və capacity. Sonrakı n sətirdə hər biri "weight value".
Çıxış verilənləri
Maksimum əldə edilə bilən dəyəri çap edin.
1Nümunə 1:
Giriş:
4 7
1 1
3 4
4 5
5 7
Çıxış:
9
İzah:2-ci (çəki 3, dəyər 4) və 3-cü (çəki 4, dəyər 5) əşyalar: cəmi çəki 7 (tutuma bərabər), dəyər 4+5=9
2Nümunə 2:
Giriş:
3 50
10 60
20 100
30 120
Çıxış:
220
İzah:2-ci və 3-cü əşyalar: 100+120=220, çəki 50
Məhdudiyyətlər
1 ≤ n ≤ 1000
1 ≤ capacity ≤ 1000
REDAKTOR
Giriş edin
Kodu yoxlamaq üçün "Göndər" düyməsinə basın
Giriş:
4 7
1 1
3 4
4 5
5 7
Çıxış:
9