Жадный алгоритм в задаче о рюкзаке/Задачи/sorted weight and cost — различия между версиями
StasFomin (обсуждение | вклад) |
Abondar (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
− | + | '''Алгоритм:''' | |
− | Предположим, что в | + | В этом случае можно использовать наиболее тривиальный алгоритм: набирать предметы в рюкзак в отсортированном порядке. |
+ | |||
+ | '''Корректность:''' | ||
+ | |||
+ | Предположим, что полученное решение <math>M_{greedy}</math> не является оптимальным, что означает что верно утверждение: | ||
+ | |||
+ | - В оптимальном наборе <math>M_{opt}</math> есть предмет, которого нет в нашем, но при этом в нем нет некоторого предмета, который есть в нашем. | ||
+ | (истинность этого утверждения очевидна: если выполнено только первое условие, то значит <math>M_{greedy} \subset M_{opt}</math>, что значит наш алгоритм мог сделать еще шаг | ||
+ | если выполнено только первое, то по той же причине <math>M_{opt} \subset M_{greedy}</math> - тоже противоречие. | ||
+ | если же ни одно из условий не выполненио, то <math>M_{opt} = M_{greedy}</math>) | ||
+ | |||
+ | При этом отсортируем обьекты в <math>M_{greedy}</math> и <math>M_{opt}</math> и рассмотрим обьект, которого нет в нашем наборе, но есть в оптимуме (до него наш алгоритм не дошел), при этом получеатся что у этого обьекта вес больше, а цена меньше, чем у обьекта <math>M_{greedy}</math>, не присутствущего в оптимальном наборе. Значит в оптимальном наборе можне заменить предмет на более дорогой, что приводит нас к проитворечию. | ||
+ | Предположим найденное решение не совпадает с оптимумом. Значит в оптимальном наборе есть предмет , которого нет в нашем наборе, и нет некоторого предмета , который есть в нашем наборе. | ||
+ | Следовательно найденный нашим алгоритмом набор - оптимальный. | ||
+ | |||
+ | [[Категория:На проверку]] |
Версия 07:54, 7 октября 2014
Алгоритм:
В этом случае можно использовать наиболее тривиальный алгоритм: набирать предметы в рюкзак в отсортированном порядке.
Корректность:
Предположим, что полученное решение не является оптимальным, что означает что верно утверждение:
- В оптимальном наборе есть предмет, которого нет в нашем, но при этом в нем нет некоторого предмета, который есть в нашем. (истинность этого утверждения очевидна: если выполнено только первое условие, то значит , что значит наш алгоритм мог сделать еще шаг если выполнено только первое, то по той же причине - тоже противоречие. если же ни одно из условий не выполненио, то )
При этом отсортируем обьекты в и и рассмотрим обьект, которого нет в нашем наборе, но есть в оптимуме (до него наш алгоритм не дошел), при этом получеатся что у этого обьекта вес больше, а цена меньше, чем у обьекта , не присутствущего в оптимальном наборе. Значит в оптимальном наборе можне заменить предмет на более дорогой, что приводит нас к проитворечию. Предположим найденное решение не совпадает с оптимумом. Значит в оптимальном наборе есть предмет , которого нет в нашем наборе, и нет некоторого предмета , который есть в нашем наборе. Следовательно найденный нашим алгоритмом набор - оптимальный.