|
|
Строка 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>, не присутствущего в оптимальном наборе. Значит в оптимальном наборе можне заменить предмет на более дорогой, что приводит нас к проитворечию.
| + | |
− | Предположим найденное решение не совпадает с оптимумом. Значит в оптимальном наборе есть предмет , которого нет в нашем наборе, и нет некоторого предмета , который есть в нашем наборе.
| + | |
− | Следовательно найденный нашим алгоритмом набор - оптимальный.
| + | |
− | | + | |
− | [[Категория:На проверку]]
| + | |
Версия 23:08, 25 декабря 2014
Предположим, что в задаче о рюкзаке порядок сортировки по увеличению веса совпадает с порядком сортировки по уменьшению cтоимости. Сформулируйте эффективный алгоритм для поиска оптимального решения этой разновидности задачи о рюкзаке и обоснуйте его корректность.