Объяснение и реализация на Python
Задача о рюкзаке — классическая задача оптимизации в области информатики и исследования операций. Проблему можно описать следующим образом:
У вас есть набор предметов, каждый из которых имеет свой вес и ценность, а также рюкзак, который может выдержать максимальный вес. Цель состоит в том, чтобы определить наиболее ценную комбинацию предметов, которую можно положить в рюкзак, не превышая при этом его предел по весу.
Существует несколько вариантов задачи о рюкзаке:
- Рюкзак 0/1: каждый предмет можно либо включить в рюкзак, либо исключить из него (т. е. каждый предмет можно взять не более одного раза). Это называется задачей о рюкзаке 0/1, поскольку для каждого предмета выбор двоичен: либо вы берете его (1), либо нет (0).
- Дробный рюкзак: предметы можно разбить на более мелкие части, поэтому вы можете взять часть предмета, а не весь предмет. Эту версию можно решить с помощью жадного алгоритма, а задачу о рюкзаке 0/1 — нет.
- Несколько рюкзаков. Рюкзаков несколько, и цель состоит в том, чтобы оптимально наполнить каждый из них.
- Неограниченный рюкзак: у вас есть неограниченное количество каждого предмета, и цель состоит в том, чтобы определить, сколько каждого предмета нужно включить, чтобы максимизировать общую ценность, не превышая предела веса.
Формально задачу о рюкзаке 0/1 можно описать так:
Данный:
- n элементов
- Массив w[1…n], представляющий веса элементов.
- Массив v[1…n], представляющий значения элементов.
- Максимальный вес Вт
Максимизировать:
При условии:
Максимизируя целевую функцию, мы пытаемся получить максимально возможное значение в пределах ограничения веса рюкзака.
Решение грубой силы
Решение грубой силой — это простой метод решения проблемы, в котором перебираются все возможные решения, пока не будет найдено правильное. Для задачи о рюкзаке метод грубой силы включает в себя создание всех возможных комбинаций предметов и проверку того, какая комбинация обеспечивает максимальное значение без превышения предела веса рюкзака.
Для n элементов будет2^n решений. Следовательно, временная сложность этой задачи составит O(2^n), если мы воспользуемся решением методом грубой силы. Это будет худшее решение.
Предположим, у нас есть четыре различных предмета, каждый из которых имеет свою уникальную ценность и вес. Наш допустимый вес составляет 7 кг.
weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 7 items = ['item1', 'item2', 'item3', 'item4']
Давайте напишем функцию перебора.
from itertools import combinations
def knapsack_bruteforce(weights, values, capacity):
n = len(weights)
max_value = 0
best_combination = []
# Generate all possible combinations of items
for r in range(1, n + 1):
for combination in combinations(range(n), r):
total_weight = sum(weights[i] for i in combination)
total_value = sum(values[i] for i in combination)
# Check if the total weight is within capacity and the value is greater than the current max value
if total_weight <= capacity and total_value > max_value:
max_value = total_value
best_combination = combination
# Return the items in the best combination and the max value
return [items[i] for i in best_combination], max_value
best_items, max_val = knapsack_bruteforce(weights, values, capacity)
best_items, max_val
"""
(['item1', 'item4'], 9)
"""
Мы используем функциюcombinations из встроенного модуля Python itertools. Эта функция используется для генерации всех возможных комбинаций элементов.
Внешний цикл (for r in range(1, n + 1):) перебирает все возможные размеры комбинаций элементов от 1 до n.
Внутренний цикл (for combination in combinations(range(n), r):) генерирует все комбинации элементов размера r.
Для каждой комбинации рассчитываются общий вес и общая стоимость.
Условие if проверяет, находится ли общий вес текущей комбинации в пределах заданной емкости и превышает ли его значение текущее лучшее значение. Если это так, он обновляет лучшее решение.
Хотя метод грубой силы прост и работает для небольших задач, он крайне неэффективен для более крупных случаев, поскольку его временная сложность экспоненциальна (O(2^n)). Даже для умеренно большого количества элементов это становится вычислительно неосуществимым.
Задача о рюкзаке 0/1 из-за ее NP-трудной природы не имеет эффективного решения за полиномиальное время для всех случаев.
Однако к наиболее популярным решениям относится подход динамического программирования, который разбивает проблему на более мелкие подзадачи и использует таблицу для хранения решений этих подзадач, чтобы избежать избыточных вычислений.
Другим распространенным методом является метод ветвей и границ, который отсекает части пространства поиска, которые гарантированно не содержат оптимального решения.
Кроме того, эвристические и аппроксимационные алгоритмы, такие как жадный алгоритм, иногда используются для более быстрого получения почти оптимальных решений, особенно для больших экземпляров. К этой проблеме также применялись генетические алгоритмы и другие метаэвристические подходы.
