Доказательство жадного алгоритма, используемого для изменения проблемы с уплотнением

Question

Нам дают массив весов $ W $ (все веса являются положительными целыми числами), и нам нужно поставить Вес внутри бункеров.Каждый корзину может удерживать максимум max_val, и каждый вес находится на большинстве max_val.Вариация состоит в том, что упорядочение весов не должно быть изменено, то есть $ w_i $ должно быть внутри бункера перед $W_j $ вставлена, для всех $ i .

Для этого заявления о проблеме, интуитивно, что мы можем видеть, что жадный подход наполнения корзина до его максимального значения и создание нового корзина для дальнейших весов будет производить минимальное количество мусорных веществ.Я не могу придумать официальное доказательство того, что жадный раствор оптимален.Любые подсказки или рекомендации были бы здоровы!

Answer 1

Пусть $ g $ - решение, создаваемое жадным алгоритмом. Для каждого другого решения $ S $ , пусть $ I (S) $ Будьте индекс первого веса При котором $ S $ расходится от $ g $ . Пусть $ O $ - это оптимальное решение, максимизирующее $ I (O) $ . Таким образом, $ g $ Места $ i (o) $ в bin $ j $ (для некоторого $ j $ ) и $ o $ SPAN CLASS= «Математический контейнер»> $ I (O) $ в Bin $ J + 1 $ . Если мы переместим $ i (o) $ bin $ J $ (что возможно, поскольку класс SPAN= «Математический контейнер»> заказывается $ O $ , получим решение $ o '$ Используя максимально возможное, как многие консервные банки, как <класс Span= «Математический контейнер»> $ o $ , и удовлетворяющий $ I (O ')> I (O) $ . Это противоречит выбору $ O $ .

Если мы попытаемся запустить этот аргумент на неограниченном алгоритме упаковки Bin, у нас возникнут проблемы при перемещении $ I (O) $ для Bin $ j $ , поскольку в том, что ящик может быть занят другими элементами, не оставляя достаточно места для $ I (O) $ . В варианте вы считаете, это не может произойти.