Код основан на книге "Грокаем Алгоритмы" Адитьи Бхаргавы
Задача о рюкзаке (англ. knapsack problem) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.
Такую задачу можно решить методом динамического программирования, для которого справедливо:
- Динамическое программирование применяется при оптимизации некоторой характеристики.
- Динамическое программирование работает только в ситуациях, в которых задача может быть разбита на автономные подзадачи.
- В каждом решении из области динамического программирования строится таблица.
- Значение ячеек таблицы обычно соответствует оптимизируемой характеристике.
- Каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи.
- Не существует единой формулы для вычисления решений методом динамического программирования.
В данном случае задача звучит так: предположим, что вы собираетесь в турпоход. Ёмкость вашего рюкзака составялет 6 фунтов, и вы можете взять предметы из следующего списка. У каждого предмета имеется стоимость; че она выше, тем важнее предмет:
- вода, 3 фунта, 10;
- книга, 1 фунт, 3;
- еда, 2 фунта, 9;
- куртка, 2 фунта, 5;
- камера, 1 фунт, 6
Как выглядит оптимальный набор предмета для похода?
Для решения построим таблицу n x m, где
- n - общее число всех предметов (в данном случаем 5).
- m - количество подрюкзаков (6 - от 1 до 6).
То есть строки таблицы представляют предметы, а столбцы - ёмкости подрюкзаков.
Дальше в ячейках таблицы указываем стоимость набора предметов, причём по одной постоянной формуле:
Пример заполенения таблицы (в нашем случае):
В последней ячейке таблицы будут храниться - максимальная ценность заполненного рюкзака (возможно останется ещё свободное место) и набор оптимальных предметов.
В файле input.txt описываются исходные данные задачи. В первой строке идет вмещаемость рюкзака (6 фунтов):
6
Дальше в нескольких строках указывается предметы по таким правилам: через пробел идут сначала название, потом размер предмета (в фунтах), а в конце его ценность предмета. Например куртка в 2 фунта и ценностью 5:
куртка 2 5
Для представления размера и ценности предмета используется тип данных Decimal для более точной работы с вещественными числами. В частности для размеров предметов - это получения остатка от деления. Суть в том что размеры предметов могут быть не целыми числами, и в то же время нужно найти минимальный-оптимальный шаг размеров подрюкзаков, то есть рассматриваются все размеры предметов и размер всего рюкзака и находится наибольший общий делитель (НОД) этих чисел - шаг подрюкзаков. Для этого используется ускоренный алгоритм нахождения НОД при помощи взятия остатка от деления.