Жадный алгоритм в задаче о рюкзаке/Задачи/sorted weight and cost

Материал из DISCOPAL
Перейти к: навигация, поиск

Алгоритм:

В этом случае можно использовать наиболее тривиальный алгоритм: набирать предметы в рюкзак в отсортированном порядке.

Корректность:

Предположим, что полученное решение не является оптимальным, что означает что верно утверждение:

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.