Жадина.
Пришла я тут в Сочи в модную хинкальную и заказала целую гору еды. Если точнее, то 3 хинкали с говядиной, 3 с грибами и шашлык из свинины. Когда еда оказалась на столе, я осознала, что я пожадничала – как ни старайся, я столько не осилю. Но деваться некуда, заказ сделан, и я просто обязана съесть на максимально возможную долю из оплаченного чека.
Оптимизация! Задача оптимизации. Может быть позвать на помощь еще одну жадину – жадный алгоритм?
Жадный алгоритм (greedy algorithm) – это когда мы на каждом шаге делаем локальный наилучший выбор, надеясь на то, что в конце концов общее решение будет оптимальным.
Цель оптимизации – живот, заполненный на максимально возможную сумму. Оптимизируем мы, конечно, в условиях заданных ограничений. В случае с хинкальной, ограничением служу я, точнее мой желудок (в идеальном мире я бы хотела съесть все, но тогда и решать тут нечего).
За один прием пищи желудок вмещает не больше 550 грамм еды. Ем я только целыми кусочками шашлыка или целыми хинкали (ну потому что неприлично и считать неудобно).
На тарелках у нас:
- порция шашлыка весом в 100 грамм, состоящая из 5 одинаковых кусочков – свиное удовольствие за 600 рублей
- три хинкали с бараниной по 70 грамм, 333 рубля за штуку
- три хинкали с грибами по 100 грамм, 400 рублей за штуку
Классической жадине сначала необходимо найти соотношение стоимости и веса каждой тарелки еды, затем расположить их по убыванию – так жадина узнает, что нужно есть первым делом.
При каждой смене блюд проверяется условие: суммарно съеденная еда плюс то, что сейчас в тарелке, меньше вместимости желудка? Если да, то приступаем к новому блюду. Если нет, то ищем ту долю еды из тарелки, которую все-таки сможем съесть.
Попробуем? Нет, не хинкалину. Алгоритм.
Цена грамма шашлыка: 600/100=6 рублей Грамма хинкали с бараниной: 999/210=4,76 рубля Грамма хинкали с грибами: 1200/300=4 рубля
Выходит, жадине надо начинать с шашлыка. Все 5 кусочков суммарным весом в 100 грамм прекрасно помещаются в живот. После шашлыка, согласно коэффициенту стоимости, нужно переходить к хинкали с бараниной. И они тоже проглочены жадиной, вкуснятина! А вот все три грибные хинкалины не влезают: 100 шашлыка + 210 с бараниной + 300 с грибами это уже 610 грамм.
А значит пора переходить к доле. Жадина берет одну хинкалину с грибами, суммарно 410 грамм – супер, можно съесть. Еще одну – и выходит 510 грамм. Все, последняя хинкалина уже не войдет.
Считаем деньги, сколько жадина смогла нажадничать: 600 рублей шашлык, 999 рублей три хинкалины с бараниной, 800 рублей две с грибами. Итого 2399 рублей.
Молодец? Конечно.
Но что если попробовать так:
- я пожалуй съем все хинкалины, вообще все: 510 грамм за 2199 рублей,
- а потом начну есть шашлык, по кусочкам: возьмем один, 20 грамм, получим 530 грамм в животе, потом еще – и вот, ровно 550. Два кусочка шашлыка - 240 рублей. Итого 2439 рублей.
Ало, жадина, где 40 рублей? Зажала?
Да нет. Просто жадничать – не всегда выгодно. Не жадничайте где ни попадя, друзья.
Ну или хотя бы убедитесь, что множество ваших хинкалин является матроидом.
Шучу. Просто ешьте. Я пока считала – у меня все остыло.
