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

В этой статье мы разберем некоторые решения этой проблемы.

Описание

Учитывая вместимость рюкзака 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 . Заинтересованы в хакинге роста? Ознакомьтесь с разделом Схема.