Различные методы решения задачи о рюкзаке

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

Учитывая вес и стоимость n предметов, положите эти предметы в рюкзак вместимостью W, чтобы получить максимальное общее значение в рюкзаке.

Другими словами, постановка задачи о рюкзаке 0/1 может быть объяснена следующим образом: при наличии двух целочисленных массивов val [0..n-1] и wt [0..n-1], которые представляют значения и веса, связанные с n элементами соответственно и целое число W, которое представляет вместимость ранца, найдите подмножество максимального значения val [], такое, что сумма весов этого подмножества меньше или равна W. Не выбираю (свойство 0–1).

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

МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ KNAPSACK

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

1) Динамическое программирование:

Динамический алгоритм - это метод разработки алгоритма, который можно использовать, когда проблема разбивается на более простые подзадачи. Везде, где есть рекурсивное решение, которое повторяет вызовы одних и тех же входных данных, его можно оптимизировать с помощью динамического программирования. Идея состоит в том, чтобы просто сохранить результаты подзадач, чтобы их не нужно было повторно вычисляется при необходимости позже. Таким образом, этот алгоритм использует тот факт, что оптимальное решение общей проблемы зависит от оптимального решения ее подзадач. Эта простая оптимизация сокращает временные сложности от экспоненциального до полиномиального. Он решает проблемы, отображающие свойства перекрывающихся подзадач и оптимальной подструктуры обоих из которых присутствуют в задаче о рюкзаке 0–1.

Сложность времени : O (N * W).
где «N» - количество элементов веса, а «W» - вместимость рюкзака.

2) Жадный алгоритм:

Жадный - это алгоритмический метод, который строит решение по частям, всегда выбирая следующую часть, которая дает наиболее очевидную и немедленную выгоду. Таким образом, проблемы, в которых выбор локально оптимальных решений также приводит к глобальному решению, лучше всего подходят для Greedy. Этот метод в основном используется для Дробной задачи о ранце. Основная идея жадного подхода в этой задаче состоит в том, чтобы вычислить соотношение цена / вес для каждого элемента и отсортировать его на основе этого отношения. Затем возьмите элемент с наибольшим соотношением и добавляйте их до тех пор, пока мы не сможем добавить следующий элемент целиком, а в конце добавьте следующий элемент, насколько это возможно. Это всегда будет оптимальным решением данной проблемы.

Но жадный алгоритм не всегда дает оптимальное решение для задачи о ранце 0/1, потому что этот алгоритм не всегда учитывает весь объект, но может также учитывать и часть объекта, чтобы сохранить вместимость ранца и максимизировать прибыль. Но в задаче о рюкзаке 0/1 мы не можем рассматривать часть объекта и должны рассматривать только весь объект. Таким образом, можно видеть, что жадный метод не всегда гарантирует оптимальное решение проблемы 0/1, но работает для дробного.

Сложность времени: O (n * logn)

При использовании простого алгоритма сортировки (выбор, пузырь) сложность всей проблемы составляет O (n²).

При использовании быстрой сортировки или сортировки слиянием сложность всей проблемы составляет) O (n * logn). Поскольку основным шагом времени является сортировка, всю проблему можно решить только за O (n * logn).

3) Алгоритм перехода и границы:

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

Этот алгоритм основан на дереве пространства состояний. Дерево пространства состояний - это корень дерева, где каждый уровень представляет решение в пространстве решений, которое опирается на верхний уровень, а любое мыслимое решение представлено несколькими способами, начиная с корня и заканчивая листом. Корень остается на уровне 0 и представляет состояние, в котором не было принято неполное решение. На листе нет молодых людей, и он представляет собой состояние, в котором все решения, составляющие ответ, были приняты.

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

Сложность времени : O (2n)

В худшем случае алгоритм сгенерирует все промежуточные этапы и все листья. Следовательно, дерево будет полным, тогда временная сложность = O (2n)

ЗАКЛЮЧЕНИЕ:

Жадный алгоритм кажется наиболее эффективным (временная сложность), но он не дает правильного оптимального решения для задачи о рюкзаке 0/1. Метод динамического программирования также очень эффективен и является наиболее подходящим алгоритмом для решения задачи о рюкзаке 0/1 в целом, но объем памяти, используемый этим методом, является самым высоким среди трех рассмотренных подходов. Таким образом, наиболее эффективным подходом к задаче о ранце из трех является метод ветвей и границ. Он прост и удобен в применении, и его можно применять для решения задачи о рюкзаке в любых обстоятельствах.

Приведенная выше статья - это краткое изложение того, что я узнал о задаче о рюкзаке 0/1. Хотя он не охватывает всего, он может дать общее представление о проблеме и различных методах ее решения. Надеюсь это поможет!

Ссылка на эту статью - https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/, Сравнение и анализ алгоритмов для задачи о ранце 0/1