В своем проекте по обогащению у старших я решил ответить на распространенный, но сложный вопрос собеседования: как решить задачу о рюкзаке 0–1:
Предположим, у нас есть набор из n элементов, каждый с заданным неотрицательным значением wi и неотрицательным значением vi, где i = 1,…, n. Нам дается рюкзак грузоподъемностью Вт. Найдите максимальное значение для подмножества элементов, общий вес которых не превышает W.
Решение грубой силы
Чтобы найти метод грубой силы для решения этой проблемы, я подумал о том, какой будет наиболее прямой подход. Я рассудил, что было бы проверить все возможные подмножества элементов, общий вес которых ≤ W, и получить набор с максимальным значением.
Каждый элемент в наборе данных элементов имеет две возможности: он либо входит в оптимальное подмножество, либо нет. В начале задачи в рюкзаке нет предметов, и поэтому любой предмет, вес которого ≤ W, может быть помещен в рюкзак. Это означает, что любой предмет, добавленный впоследствии в рюкзак, должен быть ≤ W -Sum (w1 +… + wm), где m = количество предметы в рюкзаке. Когда больше нет предметов для исследования, возвращается сумма значений предметов в рюкзаке. Таким образом, решение методом перебора решается с использованием рекурсии:
function maxKnapsack(values, weights, W, i) {
if (W === 0 || i === 0) {
return 0;
if (weights[i] > W)
return maxKnapsack(values, weights, W, i-1);
else
let included = values[i] + maxKnapsack(values, weights, W-weights[i], i-1);
let excluded = maxKnapsack(values, weights, W, i-1);
return Math.max(included, excluded);
}
В дополнение к значениям и весам элементов, а также допустимому весу, функция должна иметь возможность принимать значение индекса в качестве параметра (эта функция предполагает, что начальное значение начинается с items.length-1, но это может быть переписан так, чтобы он начинался с 0 и заканчивался на items.length). Поскольку не гарантируется, что элемент будет включен в оптимальное решение, если он ≤ текущей грузоподъемности, возвращаемое значение является максимальным между результатом, когда элемент включен в решение, и результатом, когда элемент не включен. включены в раствор. По сути, эта функция разбивает каждую подзадачу на две более мелкие подзадачи и оценивает их. Это означает, что в наихудшем сценарии количество вызовов функции равно 2 ^ n, что означает, что решение методом перебора имеет временную сложность O (2 ^ n). Хотя это не проблема, когда n мало, когда n становится большим, время, необходимое для поиска оптимального значения, становится непомерно высоким.
Оптимизированное решение
Причина низкой эффективности времени выполнения для решения методом грубой силы заключалась в том, что ему необходимо было проверить каждое возможное подмножество элементов, общий вес которых находился в пределах ограничений. Это часто означало решение подзадач более одного раза, поскольку они перекрывались, поскольку мы не хранили ответы, и у нас не было никаких средств их переноса. Таким образом, нам нужен какой-то кеш для мемоизации.
Важно помнить, что сумма весов элементов, используемых в оптимальном решении, не обязательно должна быть в точности равной W; сумма весов также может быть ‹W. Таким образом, другим способом анализа подмножества является создание двумерной таблицы оптимальных значений, где ось Y представляет максимальное количество предметов, разрешенных в рюкзаке и указателе, а ось X представляет значение W. Чтобы помочь в визуализации, предположим, что нам даны следующие данные:
- items = [{значение: 6, вес: 1}, {значение: 10, вес: 2}, {значение: 12, вес: 3}]
- W = 5
Таблица ниже будет выглядеть примерно так:
0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 6 6 6 6 6 2 0 6 10 16 16 16 3 0 6 10 16 18 22
Элемент в нижней и самой правой ячейке - это значение оптимального подмножества предметов для рюкзака. Оптимальное решение - создать таблицу, в которой каждое значение в столбце каждой строки равно max (значение соответствующего значения элемента индекса + наибольшее значение в таблице, чей соответствующий вес элемента + вес текущего элемента ≤ W, значение ячейки в предыдущей строке и том же столбце). Когда он будет полностью заполнен, верните самое нижнее правое значение.
function maxKnapsack(items, W) {
let cache = [];
for (g = 0; g < items.length+1; g++){
cache[g] = [];
for (h = 0; h < W+1; h++) {
cache[g][h] = 0;
}
}
let weights = items.map(item => item.weight);
let values = items.map(item => item.value);
for (let i = 0; i < items.length+1; i++) {
for (let j = 0; j < W+1; j++) {
if (i ==== 0 || j === 0)
cache[i][j] = 0;
else if (weights[i-1] <= j) {
let included = values[i-1] + cache[i-1][j-weights[i-1]];
let excluded = cache[i-1][j];
cache[i][j] = Math.max(included, excluded);
}
else
cache[i][j] = cache[i-1][j]
}
}
return cache[items.length][W];
}
Поскольку сформированная таблица имеет размер nW, это решение имеет эффективность использования времени и пространства, равную O (nW).
Прочие примечания
Основная трудность задачи о рюкзаке 0–1 как вопроса на собеседовании заключается в том, что, хотя необходимость динамического программирования очевидна, количество подзадач, на которые оно может быть разбито, значительно меньше. Оптимизация также сложна, так как в зависимости от приведенных примеров время выполнения решения методом грубой силы может показаться более эффективным по времени, что может запутать ситуацию. Например, если W = 70, а набор элементов имеет вид [{значение: 70, вес: 10}, {значение: 80, вес: 15}, {значение: 100, вес : 20}, {значение: 130, вес: 25}, {значение: 140, вес: 35}, {значение: 160, вес: 40}], затем худшее время для решения методом перебора = 2⁶, или 64 , а время оптимального решения = 6 * 70 = 420.
Решение проблемы с рюкзаком 0–1 также более неудобно в Javascript, чем в других языках, потому что Javascript не позволяет легко объявлять размерный массив. Хотя это второстепенный момент, его стоит иметь в виду.
Мой LinkedIn: https://www.linkedin.com/in/alexmorson/
