Задача о рюкзаке

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

Для примера рассмотрим следующий пример

У нас есть рюкзак (квадрат с черной рамкой) вместимостью 10. Есть 6 предметов (4 в рюкзаке и 2 слева от квадрата). Каждый предмет имеет вес (значение красного цвета) и стоимость (значение черного цвета). В данном примере максимальная стоимость предметов, которые можно положить в рюкзак - 42 (9 + 8 + 15 + 10). Общий вес этих предметов - 9 (2 + 2 + 3 + 2), что меньше вместимости рюкзака (10).

Для решения задачи о рюкзаке нам понадобится общий класс Knapsack с методом maxValue

Каждый отдельный предмет - экземпляр класс Item. У каждого предмета есть стоимость (cost) и вес (weight). Также переопределим метод toString()

Brute force

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

Основная идея такого принципа следующая. Каждый предмет может или быть, или не быть в рюкзаке. Всего у нас 6 предметов (рис 1). Мы можем представить предметы следующим образом

Единица в данном случае - предмет включен, 0 - нет. Что то напоминает? Да, это двоичное представление числа. Сразу можно заметить, что полный перебор будет по времени выполнения займет 2 в степени количество предметов.

С помощью перебора решение будет выглядеть следующим образом.

Во-первых, мы будем представлять предметы с помощью типа int, в котором 4 байта, или 32 бита. Это значит, что мы можем представить только 32 предмета. Чтобы не запутаться со знаком, т.к. int в Java знаковый, ограничимся 31 байтом. В итоге, если количество предметов больше, чем 31 - выбрасываем исключение. Это можно сделать еще и потому, что при таком количестве предметов полный перебор начинает занимать довольно много времени.

Во-вторых, скорее всего нам хочется получить не только максимальную стоимость предметов, которые можно уложить в рюкзак, но и сами эти предметы. Для результатов заведем переменные result типа ArrayList и maxCost типа int.

Теперь о самом методе. В классе Integer есть метод Integer.toBinaryString(int value), который принимает число и возвращает строку, содержащую двоичное представление числа. Используем этот метод, чтобы самим не заниматься преобразованием числа в двоичный формат.

Метод String.format позволяет форматировать строку. Добавим метод, который получает число и возвращает двоичное представление в виде строки заданной длинны, заполняя пробелы нулями

Если теперь в цикле передать постоянно увеличивающее значение, начиная с 0 и до 2 в степени количество предметов, мы получим все возможные комбинации вхождения предметов (показаны значения только первых и последних вызовов).

Метод formResult добавляет в список только те предметы из списка items, у которых в соответствующем разряде стоит "1". Да, перевод числа в строку для последующего перебора всех вариантов, учитывающий символ как "1" не быстрый, но мы никуда не спешим. Способ сам по себе не быстрый.

Итоговый метод maxValue класса KnapsackBruteForce

В строках с 15 по 20 добавляем вес и стоимость для конкретной битовой строки. Если получившийся вес меньше вместимости рюкзака и стоимость получившейся строки больше текущего максимума (строка 22) - изменяем максимум стоимости и формируем новый итоговый список. Строка 28 выводит все элементы итогового листа, а 29 - итоговую максимальная стоимость.

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

Жадный способ

Жадный способ предполагает, что мы берем сначала наиболее ценные предметы. Сразу стоит отметить, этот способ дает приближенное значение, не самое точное.

Если мы будем просто брать самые дорогие вещи, не учитывающие их вес, то получим довольно слабые результаты. Лучше ориентироваться не на стоимость, а на стоимость на 1 единицу веса, или удельную стоимость.

Решение заключается в следующем

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

Добавим вспомогательный класс UnitCostItem, содержащий удельную стоимость (умножение в конструкторе на 1.0 нужно т.к. иначе мы получим целочисленное деление)

Метод maxValue класс GreedyKnapsack выглядит так. Создаем список объектов UnitCostItem, сортируем, формируем результирующий список, выводим список и возвращаем сумму стоимости результирующего списка.

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

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

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

Чтобы понять как устроено решение с помощью динамического программирования, рассмотрим следующий случай. У нас есть рюкзак размером 5 и 2 предмета: первый весом 2 и стоимостью 3, второй весом 4 и стоимость 4. На изображении ниже квадратом представлены предметы, в которых черным цветом обозначен вес, а зеленым - стоимость. В кружках обозначена вместимость рюкзака.

Если у нас есть 2 предмета, то второй предмет мы можем взять, а можем не брать. Если мы возьмем второй предмет, то нам нужно рассмотреть туже задачу, но меньшего размера - количество предметов уменьшается на 1, а общий вес рюкзака уменьшается на вес этого предмета (5 - 4 = 1). Если мы не берем этот предмет - количество предметов уменьшается на 1, но вес рюкзака остается таким же (5).

Какой вариант выбрать? Тот, который лучше (с большей ценностью). Но какой из них лучше, пока непонятно.

Повторим эти размышления, когда у нас остается только 1 предмет в рюкзаке, и мы не взяли второй предмет (начиная со стрелки не берем 2 предмет). У нас остался 1 предмет и рюкзак вместимостью 5. Вес предмета равен 2, он помещается в рюкзак но мы также можем его не брать. Если возьмем - максимальная стоимость увеличится на стоимость этого предмета (в данном случае на 3), вместимость рюкзака уменьшится на вес этого предмета (в данном случае на 2), а количество предметов будет равно нулю.

Таким образом, если у нас есть только 1 предмет, который имеет хоть какую то стоимость и влезает в рюкзак - нам нужно его взять. В данном примере, если мы возьмем предмет максимальная стоимость будет равна 3, а если нет - 0.

Если мы возьмем 2-ой предмет, то ситуация похожая. Общая стоимость равна стоимость 2 предмета (в данном случае 4) + лучшее решение для задачи из 1 предмета и рюкзака весом 1 (5 - вес 2 предмета). Первый предмет не помещается в рюкзак вместимостью 1, поэтому мы его не берем.

Итак, мы рассмотрели оба случая - если мы берем и не берем второй предмет. Затем рассмотрели случаи, когда берем и не берем первый предмет (до тех пор, пока список предметов не станет пустым). И пришли к выводу, что если мы его берем - наибольшая стоимость равна 4, а если нет - то 3. Какую из этих ветвей выбрать? Очевидно с большей стоимостью.

Крайним случаем была ситуация, когда у нас или пустой список объектов, или рюкзак вместимостью 0. В обоих случаях максимально возможное значение стоимости - 0.

Вернемся к задаче, когда у нас только 1 предмет весом 2 и стоимостью 3 и рюкзак вместимостью 5. Рассмотрим эту задачу, как если бы у нас были все рюкзаки меньшего размера, от 5 до 1. Тогда решение было бы довольно простым.

На рис 4(слева) представлены все возможные варианты. Если у нас рюкзак вместимостью 1, мы не может поместиться в него предмет весом 2. Если рюкзак вместимость больше или равного 2, в него помещается этот предмет и максимальная стоимость будет равна стоимости этого предмета (в данном случае 3).

Но что будет, если мы добавим еще один предмет, весом 4 и стоимостью 4 (рис 4, справа). В рюкзак вместимостью 1 не влезает ни один предмет, поэтому максимальная стоимость при рюкзаке вместимостью 1 и с 2-мя предметами - 0. При рюкзаке вместимостью от 2 до 3 может поместиться только предмет весом 2. А вот в рюкзак весом 4 может поместиться как первый, так и второй предмет. Мы выбираем предмет с наибольшей стоимость.

Что будет, если мы возьмем рюкзак побольше, например вместимостью 6? Результат будет следующий

При вместимости 6 влезают оба предмета. Как мы к этому пришли.

Добавим к списку предметов нулевую строку, что соответствуем переданному пустому списку предметов. Какой максимальный вес можно унести при пустом списке предметов? Ответ 0. Добавим также рюкзак вместимостью 0. Какую максимальную стоимость можно положить в рюкзак вместимостью 0? Ответ также 0. В результате мы получим следующую таблицу

Вернемся на рис 3. Когда мы рассматривался список из 2-х предметов, второй предмет можно было или брать, или нет. Если бы мы его взяли, список уменьшился на 1, вместимость мешка на вес второго предмета а стоимость увеличилась на стоимость второго предмета. На рис. 5 сверху изображен этот случай, красные кружок с весом 4 - то, где мы находимся, остальные 2 кружка куда можем перейти. Т.е. мы можем перейти или на строку выше (если не берем предмет, вместимость рюкзака остается), или на строку выше для рюкзака вместимостью меньше на вес данного предмета(если берем рюкзак). Нам нужно взять наибольшее значение стоимости.

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

Решение

Теперь как выглядит решение задачи в общем виде. Мы создаем матрицу, строки которой отвечают за все предметы, а столбцы - за рюкзаки всех вместимостей от 1 до заданного лимита. В данном случае у нас есть k предметов, каждый предмет - i с его числовым индексом. Также есть N рюкзаков, от N до 1 вместимостью каждый. Каждая ячейка в такой матрице - максимальное значение, которое можно получить при количестве предметов k и вместимостью рюкзака N.

Для нахождения этого значения, нам нужно найти максимум из двух вариантов

• или мы берем предмет k при вместимости рюкзака N, тогда maxValue(N, k) = cost(k) + max(N - k.weight, k - 1)
• или мы не берем предмет k при вместимости рюкзака N, тогда maxValue(N, k) = max(N, k - 1)

Итоговая формула такая

maxValue(N, k) = Max(cost(k) + maxValue(N - k.weight, k - 1), max(N, k - 1)

Решение будет выглядеть следующим образом

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

Метод, рассчитывающий каждое значение. Строка 8 - это и есть формула выше. Изначально вся матрица заполняется нулями и начинаем рассчитывать значения для 1, 2 и т.д. предметов постоянно увеличивая вес. Таким образом мы начинаем с рюкзака весом 0 и одним предметом.

Метод print написан специально для визуального представления матрицы

Результат

Можно заметить, что мы наши не только вешение для списка предметов k и рюкзака вместимостью N, но и решение для всех задач меньшего объема. Сложность такого решения k x N.

Теперь можно подумать, что мы нашли максимальную ценность, но не знаем какие предметы мы взяли. Однако их можно найти за линейное время. Если мы не взяли предмет k(i) при весе N, то значение k(i - 1) при весе N будет таким же. Если они отличаются, мы взяли предмет. Какой следующий предмет, который мы могли взять? Он равен k(i-1) при N = N - вес i-го предмета. Изображение ниже демонстрирует этот прием

Заключение

Мы рассмотрели три способа решения задачи о рюкзаке

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

посмотреть примеры можно здесь.