0/1 Отстраняване на проблема с раницата с помощта на пример за динамично програмиране

Какъв е проблемът с раницата?

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

Вход:

• Максимално тегло M и брой опаковки n.
• Масив с тегло W[i] и съответната стойност V[i].

Изход:

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

Алгоритъмът Knapsack се разделя на два добре познати варианта:

• 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 е базовият случай, запълнен с нули.
• Използвайте ред 0, за да изчислите ред 1, ред 1, за да изчислите ред 2 и продължете, докато ред n не бъде завършен.

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

Trace

След като Б е завършено, фокусирайте се върху B[n][M], оптималната обща стойност за всички n пакета с капацитет M.

• If B[n][M] = B[n-1][M], пакет n не е избран, така че продължете tracот B[n-1][M].
• If B[n][M] ≠ B[n-1][M], пакет n беше избран, така че продължете tracот B[n-1][M – W[n]].

Повторете, докато стигнете до ред 0 на таблицата.

Алгоритъм за търсене на таблицата с опции за намиране на избраните пакети

Забележка: винаги когато 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--;
    }
}

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

Обяснение на кода:

1. Разпределяне на таблица B[][] и инициализирайте всяка клетка с 0.
2. Попълнете B[][] отдолу нагоре, използвайки рекурентността от предишния раздел.
3. Започнете всяка клетка със стойността „пропускане на пакет i“ B[i-1][j].
4. Ако избирането на пакет i е възможно и дава строго по-добра стойност, презапишете клетката.
5. Trace избраните елементи от ред 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 Knapsack остава NP-труден, въпреки че динамичното програмиране е ефективно на практика.

Приложения на проблема с раницата 0/1

• Товарене на товари, опаковане на контейнери и комплектоване от склад под ограничения на теглото.
• Разпределение на бюджета между инвестиционни проекти с фиксирани разходи и очаквана възвръщаемост.
• Проблеми с рязането на материал в производството, при които не е възможно разделяне на отделни парчета.
• Криптографски схеми като Merkle-Hellman, които се основават на твърдостта на раницата.
• Планиране с ограничени ресурси в облачните изчисления и разпределение на задачи на процесора.
• Избор на функции в машинното обучение при фиксиран бюджет за функции.

Въпроси и Отговори