У меня есть склад, на котором я храню товар. Каждая статья занимает данный объем складских площадей, а затраты дают сумму в долларах.
Теперь, поскольку склад заполнен, и я ожидаю новой доставки, мне нужно освободить некоторое пространство - не меньше, чем займет новая доставка, но я также должен минимизировать свои потери. Другими словами, я должен опустошить не менее X кубических метров складских площадей, выбрасывая некоторые изделия, убедившись, что стоимость этих предметов является минимально возможным значением.
Пример:
Если X = 10 м3, то я предпочитаю выбрасывать предмет, который занимает 20 м3 и стоит 1000 $, чем предмет, который занимает ровно 10 м3, но стоит 2000 $.
Конечно, в реальном расчете необходимо будет выбросить более одного предмета, возможно, 5, 10 или даже 20.
То, о чем я думаю, это представить вышеупомянутую проблему в виде дерева, в котором узлы представляют объем освобожденного пространства, а ребра представляют lost value, затем ищут узлы, значения которых больше или равны X, и затем выбирают узел у которого самый низкий lost value по краям от корня дерева до этого узла.
В чем я не уверен, если это хороший подход, потому что, например, 100 единиц товара в полном дереве склада будут иметь 100 узлов на первом уровне глубины, 100 * 99 = 9900 узлов на втором уровне и т. Д., Так что это быстро начинает вызывать затруднения.
Есть ли лучший подход или даже какой-нибудь проверенный алгоритм (о котором я не знаю) для такого рода проблем?