«1. Введение

Задача о рюкзаке — это задача комбинаторной оптимизации, имеющая множество приложений. В этом уроке мы решим эту проблему на Java.

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

В задаче о рюкзаке у нас есть набор предметов. У каждого предмета есть вес и ценность:

Мы хотим положить эти предметы в рюкзак. Однако у него есть ограничение по весу:

Поэтому нам нужно выбрать предметы, общий вес которых не превышает ограничения по весу, а их общая стоимость как можно выше. Например, лучшее решение для приведенного выше примера — выбрать предмет весом 5 кг и предмет весом 6 кг, что дает максимальную стоимость в 40 долларов США в пределах ограничения веса.

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

3. Математическое определение

Давайте теперь формализуем задачу о рюкзаке 0-1 в математической записи. Учитывая набор из n элементов и ограничение веса W, мы можем определить задачу оптимизации следующим образом:

Эта задача является NP-трудной. Следовательно, в настоящее время не существует алгоритма с полиномиальным временем для ее решения. Однако для этой задачи существует алгоритм псевдополиномиального времени, использующий динамическое программирование.

4. Рекурсивное решение

Для решения этой задачи можно использовать формулу рекурсии:

В этой формуле M(n,w) является оптимальным решением для n элементов с предельным весом w. Это максимальное из следующих двух значений:

    Оптимальное решение из (n-1) элементов с ограничением веса w (исключая 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(2n).

5. Решение для динамического программирования

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

Мы также можем решить задачу о рюкзаке 0-1 с помощью динамического программирования. Чтобы использовать динамическое программирование, мы сначала создаем двумерную таблицу с размерностями от 0 до n и от 0 до W. Затем мы используем восходящий подход для вычисления оптимального решения с этой таблицей: 

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.