| 1:00p |
Задачка про рюкзак и пожарную инспекцию
Имеется куча предметов, у каждого предмета есть свой размер.
Имеется рюкзак. У него тоже есть размер. Рюкзак изначально пуст. Все предметы одновременно в рюкзак не помещаются.
Имеется заранее известная последовательность пожарных инспекций. При каждой инспекции выбирается один предмет. Если этот предмет находится вне рюкзака, за него нужно заплатить штраф. Предмет и штраф каждой инспекции также заранее известны. Штраф за один и тот же предмет может как угодно меняться от инспекции к инспекции.
Перед каждой инспекцией можно перекладывать предметы из кучи в рюкзак и наоборот. За складывание предмета из кучи в рюкзак нужно заплатить фиксированную для этого предмета цену - например, пропорционально его размеру. За выкладывание предметов из рюкзака платить не надо.
Минимизировать расходы. |