Кстати, наша задача про банкомат эквивалентна задаче про грабителя (вот видите, наши задачи полезны и в реальной жизни): Грабитель проник в банк и нашел там N золотых слитков весом w1, w2 .. WN. В его рюкзак может поместиться не более K килограмм. Какие слитки он должен выбрать, чтобы унести как можно больше золота.---Если заменить "золотой слиток весом x" на "1 купюра номиналом X", то получается задача про банкомат.
>>2006121>Если заменить "золотой слиток весом x" на "1 купюра номиналом X", то получается задача про банкомат. Очевидно нет. Банкомат должен конкретную сумму выдать, а грабитель должен взять сумму не больше K. Но можно чуть меньше.
>>2006122Нет, жадный алгоритм тут не сработает. Посмотри внимательно на ситуацию в >>2006112 . Там нет 100-рублевых купюр и жадный алгоритм не сможет выдать 600 рублей.>>2006130Грабитель пытается взять как можно больше (но не более K). Мы можем запустить алгоритм грабителя, а в конце просто посмотреть, сколько он набрал. Если это число меньше, чем требуемая сумма K, то выдать ее невозможно (иначе бы грабитель смог её собрать). Если набранное количество золота равно требуемой сумме K, то возможно.>>2006120Никакое количество проклятий не заставит stristr работать с utf-8. Надо переписывать на использование mb-функций.
>>2006180Я сижу в других тредах, где к программированию на PHP принято относиться поплёвывая свысока.Посмотрел, что за задачка здесь обсуждается. Там конкретные купюры:есть банкомат, в нём фиксированный набор купюр в 100, 500, 1000, 5000 рублей. Нужно проверить, можно ли выдать нужную сумму, и если можно, то выдать её наименьшим количеством купюр.Это, всё-таки, другая задача, чем задача о сборке рюкзака. И в данном частном случае сильно более простая, потому что любую купюру старшего номинала можно выдать купюрами меньших номиналов. Нет даже истории о купюрах в 200 и 500 рублей. Тут ДП даже и не нужно.Задача о рюкзаке намного сложнее.
>>2006219> где к программированию на PHP принято относиться поплёвывая свысокаванильный жс хуже если тебя утешит
