Я пытаюсь найти жадное решение проблемы с упаковкой в мусорное ведро онлайн. В этой проблеме есть некоторые изменения по сравнению с оригинальной проблемой упаковки бункера. Во-первых, каждая корзина имеет емкость C> 0. Кроме того, каждый элемент i имеет вес w_i <= C. Так как это проблема онлайн-упаковки, каждый элемент должен быть помещен в корзину (и больше никогда не перемещаться) до того, как будет обработан следующий элемент. Кроме того, если мы создадим новую корзину, то мы не сможем вернуться к старой корзине и поместить в нее больше элементов позже. </p>
Мой жадный алгоритм - следующее решение подбора (поместите как можно больше элементов в одна корзина, в то время как общий вес составляет менее C). Когда мы не можем уместить следующий элемент, мы создаем новую корзину.
Но мне трудно доказать оптимальность этого решения. Я попытался использовать жадный аргумент «впереди», но застрял.
Любые намеки или указания были бы хорошими!