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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
[[Category:Нерешенные задачи]]
+
'''Алгоритм:'''
  
Предположим, что в задаче о рюкзаке порядок сортировки по увеличению веса совпадает с порядком сортировки по уменьшению cтоимости. Сформулируйте эффективный алгоритм для поиска оптимального решения этой разновидности задачи о рюкзаке и обоснуйте его корректность.
+
В этом случае можно использовать наиболее тривиальный алгоритм: набирать предметы в рюкзак в отсортированном порядке.
 +
 
 +
'''Корректность:'''
 +
 
 +
Предположим, что полученное решение <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

Алгоритм:

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

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

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

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

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