Блог

Вору предоставляется выбор n предметов для кражи, но у него есть только один рюкзак, способный выдержать M вес. Каждый объект i имеет вес w_i и прибыль p_i . Предположим, он также знает следующее: порядок этих элементов при сортировке по возрастанию веса совпадает с их порядком при сортировке по уменьшению значения. Дайте жадный алгоритм для нахождения оптимального решения этого варианта проблемы с рюкзаком. Докажите правильность и время выполнения.

Итак, жадный алгоритм, который я придумал, заключался в сортировке предметов на основе увеличения веса, который также уменьшает значение. Это означает, что цена за вес находится в порядке убывания. Таким образом, вор может взять самый ценный предмет до веса >= M . Время выполнения будет составлять O(n log n) с момента сортировки O(n log n) и итерации по списку O(n) . Часть, на которой я застрял, является доказательством правильности. Вот мое доказательство до сих пор:

Предположим, что существует случай, когда указанное выше решение (называемое GA) не является оптимальным. Пусть оптимальное решение называется OS, а элементы, взятые OS, сортируются по возрастающей стоимости. Поскольку OS более оптимальна, чем GA, то прибыль, полученная от GA, меньше или равна прибыли, полученной от OS. Поскольку GA берет элемент с наибольшим соотношением прибыли и веса, то первый элемент, i , должен быть больше или равен первому элементу OS. Поскольку ОС более оптимальна, то должно существовать a i , которое больше или равно элементу j в наборе GA. Но поскольку GA и OS выполняются в одном наборе, и GA всегда берет элемент с наибольшей прибылью / весом, в OS не может быть a i , который больше, чем a j в GA.

Кто-нибудь может помочь с доказательством? Спасибо

Ваш подход к решению верен, и рассуждения о времени выполнения верны. В дальнейшем предположим, что входные данные «детривиализированы» в том смысле, что каждый возникающий объект фактически помещается в рюкзак и что невозможно выбрать весь ввод.

Сортировка элементов, генерируемых сортировкой, является как

• уменьшение значения
• увеличение веса

что делает его частным случаем общей проблемы с рюкзаком. Аргументация для доказательства правильности заключается в следующем. Пусть i' обозначим индекс разрыва, который является индексом первого элемента в отсортированной последовательности, который отклоняется жадным алгоритмом. Для ясности назовите соответствующий объект объектом breaking . Обратите внимание, что

 w_j > w_i' for each j > i'
  

выполняется, что означает, что жадный алгоритм также отклоняет каждый объект, следующий за объектом взлома (поскольку он не помещается в рюкзак, как и объект взлома).

В целом, жадный алгоритм выбирает префикс отсортированной последовательности; мы стремимся показать, что любое оптимальное решение (которое мы считаем фиксированным в дальнейшем) является тем же префиксом.

Обратите внимание, что оптимальное решение, поскольку оно является оптимальным, не оставляет места для дополнительного объекта.

Стремясь к противоречию, пусть k будет минимальный индекс, который встречается в жадном решении, но не в оптимальном решении. Поскольку невозможно дополнительно выбрать объект k в оптимальное решение, в оптимальном решении должен быть (через минимальность k ) некоторый элемент с индексом

 k' > k
  

что позволяет обмениваться элементами в оптимальном решении. Как

 w_k < w_k' and p_k > p_k'
  

удержание, объект k' может быть заменен объектом k в оптимальном решении, что дает решение с прибылью, большей, чем у оптимального решения, что противоречит его оптимальности.

Следовательно, в жадном решении нет элемента, который отсутствует в оптимальном решении, что означает, что жадное решение является подмножеством оптимального решения. С другой стороны, жадное решение является максимальным по включению, что означает, что оптимальное решение не может содержать элемент, отсутствующий в жадном решении.

Обратите внимание, что жадный алгоритм als полезен для общей задачи с рюкзаком; выбор лучшего из жадного решения и элемента с максимальной прибылью дает алгоритм аппроксимации с коэффициентом 2.