1. введение
Проблема рюкзака – это задача комбинаторной оптимизации, имеющая множество приложений. В этом уроке мы решим эту проблему на Java.
2. Проблема рюкзака
В задаче о рюкзаке у нас есть набор предметов. Каждый предмет имеет вес и ценность:
Мы хотим сложить эти вещи в рюкзак. Однако у него есть ограничение по весу:
Поэтому нам нужно выбирать предметы, общий вес которых не превышает предельного веса, а их общая стоимость как можно выше. Например, лучшим решением для приведенного выше примера является выбор 5-килограммового товара и 6-килограммового товара, что дает максимальное значение $40 в пределах ограничения веса.
Проблема рюкзака имеет несколько вариантов. В этом уроке мы сосредоточимся на проблеме рюкзака 0-1 . В задаче о рюкзаке 0-1 каждый предмет должен быть либо выбран, либо оставлен. Мы не можем взять частичное количество товара. Кроме того, мы не можем брать предмет несколько раз.
3. Математическое Определение
Давайте теперь формализуем задачу о рюкзаке 0-1 в математической нотации. Учитывая набор n элементов и предельный вес W , мы можем определить задачу оптимизации следующим образом:
Эта проблема NP-трудна. Поэтому в настоящее время не существует полиномиального алгоритма для его решения. Однако существует псевдополиномиальный временной алгоритм , использующий динамическое программирование для этой задачи.
4. Рекурсивное Решение
Мы можем использовать рекурсивную формулу для решения этой проблемы:
В этой формуле M(n,w) является оптимальным решением для n предметов с предельным весом w . Это максимальное из следующих двух значений:
- Оптимальное решение из (n-1) изделий с предельным весом ж (исключая n -й товар)
- Значение n -го пункта плюс оптимальное решение из (n-1) пунктов и w минус вес n -го пункта (включая n -й пункт)
Если вес n -го элемента превышает текущий предел веса, мы его не включаем. Поэтому он относится к первой категории из двух вышеперечисленных случаев.
Мы можем реализовать эту формулу рекурсии в Java:
int knapsackRec(int[] w, int[] v, int n, int W) {
if (n <= 0) {
return 0;
} else if (w[n - 1] > W) {
return knapsackRec(w, v, n - 1, W);
} else {
return Math.max(knapsackRec(w, v, n - 1, W), v[n - 1]
+ knapsackRec(w, v, n - 1, W - w[n - 1]));
}
}
На каждом шаге рекурсии нам нужно оценить два неоптимальных решения. Следовательно, время выполнения этого рекурсивного решения равно O(2 n ).
5. Решение для Динамического Программирования
Динамическое программирование-это стратегия линеаризации в противном случае экспоненциально сложных задач программирования. Идея состоит в том, чтобы сохранить результаты подзадач, чтобы нам не пришлось пересчитывать их позже.
Мы также можем решить проблему рюкзака 0-1 с помощью динамического программирования. Чтобы использовать динамическое программирование, мы сначала создаем 2-мерную таблицу с размерами от 0 до n и от 0 до Ж . Затем мы используем восходящий подход для расчета оптимального решения с помощью этой таблицы:
int knapsackDP(int[] w, int[] v, int n, int W) {
if (n <= 0 || W <= 0) {
return 0;
}
int[][] m = new int[n + 1][W + 1];
for (int j = 0; j <= W; j++) {
m[0][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (w[i - 1] > j) {
m[i][j] = m[i - 1][j];
} else {
m[i][j] = Math.max(
m[i - 1][j],
m[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
return m[n][W];
}
В этом решении мы имеем вложенный цикл над номером элемента n и пределом веса W . Следовательно, его время работы равно O(nW) .
6. Заключение
В этом уроке мы показали математическое определение задачи о рюкзаке 0-1. Затем мы предоставили рекурсивное решение этой проблемы с помощью реализации Java. Наконец, для решения этой задачи мы использовали динамическое программирование.
Как всегда, исходный код статьи доступен на GitHub .