Участник:Jzargo/Решение задачи про рюкзак где сортировки совпадают

Материал из DISCOPAL
Перейти к: навигация, поиск

Задача о рюкзаке, где две сортировки совпадают Просто каждый раз из самых лёгких берём самый дорогой. Т.е. если на каком-то этапе выбор по (weight,cost) между (10,5) и (10,10), мы берём второй и не проигрываем в весе, при выигрыше в стоимости. Выходит, что этот алгоритм НЕ ХУЖЕ стандартного жадного решения при сортировке по весу, а в случае равенств каких-то весов ГАРАНТИРОВАННО ЛУЧШЕ его.

StasFomin 10:46, 18 апреля 2019 (MSK): Качество стандартного жадного ниже плинтуса — для любого $k$ он может быть хуже. Можете ли вы обосновать гарантированное качество решения этого алгоритма?