Masala #40J3PORF98

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 1 %

#Ochko'z algoritm

Sumka muammosi

n ta buyum bor, ularning vazni w[i] va qiymati v[i]. Sumkaning sig‘imi M. Sumkaga buyumlarni qisman solish ham mumkin. Ushbu sumkaga solish mumkin bo'lgan buyumlarning maksimal qiymatini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda n buyumlar soni va sumkaning sig'imi(0 < n < 100000, 0 < M < 10^9). Keyingi n ta qatorda ushbu buyumlarning og'irligi va qiymati probel bilan ajratilgan holda beriladi (0 < w, v < 10000).

Chiquvchi ma'lumotlar:

Yagona haqiqiy son, sumkaga solish mumkin bo'lgan buyumlarning maksimal qiymati 3 xona aniqlikda.

Misollar

#	input.txt	output.txt
1	3 50 10 60 20 100 30 120	240.000

Izoh:

1-test uchun quyidagicha yechim optimal. Vazni 10 bo'lgan buyumni hammasini oladi, keyin vazni 20 bo'lgan buyumni hammasini oladi, so'ngra uchinchi buyumdan 20 birlik vaznda oladi. Umumiy og'irlik 50 bo'ldi, ushbu buyumlarning qiymati esa 60 + 100 + 80 = 240.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin