Masala #0594
Sumka yoki knapsack
Sizga \(n\) va \(c\) summa beriladi. \(n\) ta elementdan iborat \(v\), \(w\) to'plam beriladi. \(i\) uchun \((0 \le i \le n-1)\) \(v[i]\) - qiymat , \(w[i]\) - og'irlik. Sizning vazifangiz maksimal qiymat tanlashingiz kerak bo'ladiki, ularga mos og'irliklar yig'indisi summadan oshmasin.
Kiruvchi ma'lumotlar:
Birinchi qatorda \(n(1 \le n \le 10^3)\) va \(c(0 \le c \le 2*10^6)\) beriladi.
Ikkinchi qatorda \(n\) ta son \(v_0 , v_1, \dots, v_{n-1}\) \((0 \le v_i \le 50)\).
Uchinchi qatorda \(n\) ta son \(w_0, w_1, \dots , w_{n-1}\) \((0 \le w_i \le 50)\).
Chiquvchi ma'lumotlar:
Chiqishda bir qatorda siz tanlashingiz mumkin bo'lgan maksimal qiymat.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 20 10 15 6 4 10 5 10 10 |
25 |
Izoh:
Birinchi test uchun biz tanlashimiz mumkin maximal qiymat 25ga teng.
(10+15) ularga mos og'irliklar yig'indis (10+5) u 20 dan katta emas.
Telegram kanalimizga obuna bo'ling