Реализация задачи о рюкзаке на Java

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(2 n ).

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 .