Решение проблемы с рюкзаком 0/1 с использованием примера динамического программирования

В чем заключается задача о рюкзаке?

Проблема с рюкзаком Это классическая задача комбинаторной оптимизации. Супермаркет n упаковки (n ≤ 100). Упаковка i Вес W[i] ≤ 100, а стоимость V[i] ≤ 100. Вор не может нести груз, превышающий грузоподъемность M (M ≤ 100). Какие посылки должен взять вор, чтобы максимизировать общую стоимость?

Входной сигнал:

• Максимальный вес M и количество упаковок n.
• Массив веса W[i] и соответствующего значения V[i].

Выход:

• Максимальная суммарная стоимость, достижимая в пределах допустимой вместимости.
• Точный набор посылок, которые должен забрать вор.

Алгоритм поиска рюкзака делится на два хорошо известных варианта:

• Задача о рюкзаке 0/1 Задача решена с помощью динамического программирования. Каждый пакет либо берется целиком, либо остается нетронутым — никаких дробных частей и дубликатов.
• Задача о дробном рюкзаке Решение найдено с помощью жадной стратегии. Здесь вы можете взять часть любой упаковки, чтобы заполнить оставшуюся вместимость.

Как решить задачу о рюкзаке с помощью динамического программирования на примере

Метод «разделяй и властвуй» разбивает большую задачу на подзадачи, а затем продолжает разбиение до тех пор, пока каждая подзадача не станет простой. Однако простая рекурсия часто решает одну и ту же подзадачу много раз и приводит к пустой трате времени.

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

Решите задачу о рюкзаке с помощью динамического программирования

Для разработки решения с использованием динамического программирования необходимо выполнить четыре шага:

• Сначала решите самые мелкие подзадачи.
• Выведите рекуррентное соотношение, которое позволяет построить решение подзадачи из решений более мелких.
• Сохраняйте ответы на подзадачи в таблице, вычисленной снизу вверх с использованием рекуррентного соотношения.
• Составьте окончательный ответ, используя полностью заполненную таблицу.

Анализ задачи о рюкзаке 0/1

Оптимальное значение зависит от двух независимых факторов:

1. Сколько пакетов еще находятся на рассмотрении?
2. Оставшийся вес, который еще может вместить рюкзак.

Поскольку целевая функция зависит от двух величин, таблица вариантов должна быть двумерной. Пусть B[i][j] обозначает максимальное значение при выборе среди пакетов {1, …, i} с ограничением веса j.

• Окончательный ответ B[n][M], наилучшее суммарное значение по всем n пакетам в пределах емкости M.
• Общий выбранный вес всегда ограничен текущей грузоподъемностью: B[i][j] ≤ j.

Пример: если B[4][10] = 8, то наилучший суммарный вес первых четырех пакетов вместимостью менее 10 равен 8. Некоторые из этих четырех пакетов могут быть пропущены.

Формула для расчета B[i][j]

• W[i], V[i] — это вес и стоимость посылки i, где i принадлежит множеству {1, …, n}.
• M Это максимальный вес, который может нести рюкзак.

Базовый случай с одним пакетом: для любой емкости j ≥ W[1]:

B[1][j] = W[1]

В общем случае решите, следует ли включать пакет i в состав емкости j:

• Если пакет i пропущеноB[i][j] равно наилучшему значению при использовании пакетов {1, …, i-1} в пределах емкости j:

B[i][j] = B[i - 1][j]

• Если пакет i приняты (разрешено только при W[i] ≤ j), B[i][j] равно V[i] плюс наилучшее значение из пакетов {1, …, i-1} при емкости j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Возьмем, например, более крупного из двух кандидатов.

Основы динамического программирования

Сочетание двух случаев дает полную картину повторения:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Базовый вариант — B[0][j] = 0 для каждого j, потому что нулевые пакеты дают нулевую ценность независимо от вместимости.

Рассчитать таблицу вариантов

Постройте таблицу B, используя рекуррентное соотношение. После заполнения таблицы B та же самая таблица будет использоваться для построения следующей таблицы. trace-back, который восстанавливает выбранные пакеты. Таблица B имеет n + 1 строку и M + 1 столбец:

• Нулевая строка — это базовый случай, заполненный нулями.
• Используйте строку 0 для вычисления строки 1, строку 1 для вычисления строки 2 и продолжайте, пока не будет завершена строка n.

Таблица опций

Trace

После завершения этапа B, сосредоточьтесь на B[n][M], оптимальное суммарное значение по всем n пакетам вместимостью M.

• If B[n][M] = B[n-1][M]Пакет n не был выбран, поэтому продолжаем. tracing from B[n-1][M].
• If B[n][M] ≠ B[n-1][M]Пакет n был выбран, поэтому продолжаем. tracing from B[n-1][M – W[n]].

Повторяйте, пока не дойдете до нулевой строки таблицы.

Алгоритм просмотра таблицы параметров для поиска выбранных пакетов

Примечание: всякий раз, когда B[i][j] = B[i-1][j]Пакет i не выбран. Значение B[n][M] — это оптимальная общая стоимость, помещенная в рюкзак.

Шаги для tracиспользование выбранных пакетов:

• Шаг 1: Начните с i = n, j = M.
• Шаг 2: Просканируйте столбец j снизу вверх, пока не найдете строку i, в которой B[i][j] > B[i-1][j]. Отметьте пакет i как выбранный: Select[i] = true.
• Шаг 3: Обновите j = j – W[i]. Если j > 0, вернитесь к шагу 2, в противном случае перейдите к шагу 4.
• Шаг 4: Распечатайте все пакеты, отмеченные как выбранные.

Java Code

Следующие Java метод заполняет B[][] снизу вверх, выводит таблицу для проверки, а затем tracвыбирает пакеты.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Функция knapsackDyProg() в Java

Расшифровка кода:

1. Выделить таблицу B[][] и инициализировать каждую ячейку значением 0.
2. Заполните B[][] снизу вверх, используя рекуррентное соотношение из предыдущего раздела.
3. Начинайте каждую ячейку со значения «skip package i». B[i-1][j].
4. Если выбор пакета i возможен и дает явно лучшее значение, перезапишите ячейку.
5. TracПереместите выбранные элементы из строки n обратно в строку 0.
6. При выборе пакета n уменьшите оставшуюся емкость на W[n-1].

Примечание по исправлению: исходный фрагмент кода измененный параметр M продолжая читать B[n][M]В более безопасном варианте, представленном выше, используется отдельный курсор. j для trace.

Java Программа запускает алгоритм на двух проверенных примерах:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Результат для первого примера:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Результат для второго примера:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Временная и пространственная сложность задачи о рюкзаке 0/1

• Временная сложность: O(n · M) — два вложенных цикла перебирают n элементов в пределах M+1 состояний вместимости.
• Пространственная сложность: O(n · M) для всей таблицы, сводимое к O(M) путем keeping только предыдущая строка, когда tracЭлектронная обложка не требуется.

Время выполнения псевдополином: полиномиально от значения M, но экспоненциально от количества битов, используемых для кодирования M. Именно поэтому задача о рюкзаке 0/1 остается NP-трудной, несмотря на то, что динамическое программирование эффективно на практике.

Применение задачи о рюкзаке 0/1

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

Часто задаваемые вопросы (FAQ)