«phpClub» — архив тем ("тредов"), посвящённых изучению PHP и веб-технологий.
Аноним 2021/04/23 16:27:46  №2006121 1
Кстати, наша задача про банкомат эквивалентна задаче про грабителя (вот видите, наши задачи полезны и в реальной жизни):

Грабитель проник в банк и нашел там N золотых слитков весом w1, w2 .. WN. В его рюкзак может поместиться не более K килограмм. Какие слитки он должен выбрать, чтобы унести как можно больше золота.

---

Если заменить "золотой слиток весом x" на "1 купюра номиналом X", то получается задача про банкомат.
Ответы: >>2006130
Аноним 2021/04/23 16:36:50  №2006130 2
>>2006121
>Если заменить "золотой слиток весом x" на "1 купюра номиналом X", то получается задача про банкомат.
Очевидно нет. Банкомат должен конкретную сумму выдать, а грабитель должен взять сумму не больше K. Но можно чуть меньше.
Ответы: >>2006180
Аноним 2021/04/23 17:37:33  №2006180 3
>>2006122

Нет, жадный алгоритм тут не сработает. Посмотри внимательно на ситуацию в >>2006112 . Там нет 100-рублевых купюр и жадный алгоритм не сможет выдать 600 рублей.

>>2006130

Грабитель пытается взять как можно больше (но не более K). Мы можем запустить алгоритм грабителя, а в конце просто посмотреть, сколько он набрал. Если это число меньше, чем требуемая сумма K, то выдать ее невозможно (иначе бы грабитель смог её собрать). Если набранное количество золота равно требуемой сумме K, то возможно.

>>2006120

Никакое количество проклятий не заставит stristr работать с utf-8. Надо переписывать на использование mb-функций.
Ответы: >>2006219
Аноним 2021/04/23 19:02:28  №2006219 4
>>2006180
Я сижу в других тредах, где к программированию на PHP принято относиться поплёвывая свысока.

Посмотрел, что за задачка здесь обсуждается. Там конкретные купюры:
есть банкомат, в нём фиксированный набор купюр в 100, 500, 1000, 5000 рублей. Нужно проверить, можно ли выдать нужную сумму, и если можно, то выдать её наименьшим количеством купюр.

Это, всё-таки, другая задача, чем задача о сборке рюкзака. И в данном частном случае сильно более простая, потому что любую купюру старшего номинала можно выдать купюрами меньших номиналов. Нет даже истории о купюрах в 200 и 500 рублей. Тут ДП даже и не нужно.

Задача о рюкзаке намного сложнее.
Ответы: >>2006316
Аноним 2021/04/23 20:59:26  №2006316 5
>>2006219
> где к программированию на PHP принято относиться поплёвывая свысока
ванильный жс хуже если тебя утешит