Задача о рюкзаке — это задача комбинаторной оптимизации: для заданного набора предметов, каждый из которых имеет вес и ценность, определить количество каждого предмета, которое нужно включить в коллекцию, чтобы общий вес был меньше или равен заданному пределу и общая стоимость как можно больше. Его название связано с проблемой, с которой сталкивается тот, кто ограничен рюкзаком фиксированного размера и должен наполнить его самыми ценными предметами.
В этой статье мы разберем некоторые решения этой проблемы.
Описание
Учитывая вместимость рюкзака W = 40, список предметов values = [10, 20, 30, 40], веса = [30, 10, 40, 20]
Пример 1:
Input: w = 40, values = [10,20,30,40], weights = [30,10,40,20] Output: 60
Решение
Есть несколько вариантов решения этой проблемы:
Грубая сила рекурсии
Рекурсия создаст все подмножества предметов с общим весом меньше, чем у заданной мощности W. Из результата мы вернем подмножество с максимальным значением.
Динамическое программирование (запоминание)
При таком подходе мы будем хранить все рассчитанные ответы в hashMap с индексами ключевых элементов в строках и весами в столбцах и использовать их позже для перекрывающихся подзадач. Рекурсивный проход по-прежнему будет использоваться.
Динамическое программирование (итеративное)
Мы создаем двумерный массив (т. е. таблицу) из n + 1
строк и w + 1
столбцов (w — емкость). Номер строки i представляет набор всех элементов из строк 1 — i. Например, значения в строке 3 предполагают, что у нас есть только элементы 1, 2 и 3.
Собрав все вместе, запись в строке i столбца j представляет максимальное значение, которое можно получить с помощью элементов 1, 2, 3… i , в рюкзаке, способном вместить j единиц веса.
После того, как таблица заполнена, окончательное решение можно найти в последней строке последнего столбца, которое представляет собой максимальное значение, получаемое при всех элементах и полной емкости. рюкзака.
Алгоритм можно выразить так:
Надеюсь, это было полезно для вас!
Спасибо за прочтение! До скорой встречи. 😊
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord . Заинтересованы в хакинге роста? Ознакомьтесь с разделом Схема.