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

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

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

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

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

Вывод:

Максимизируйте ценность и соответствующий вес вместимости.
Какие пакеты унесет вор.

Алгоритм ранца можно разделить на два типа:

Задача о рюкзаке 0/1 с использованием динамического программирования. В этом типе алгоритма Knapsack каждый пакет можно взять или не взять. Кроме того, вор не может взять дробное количество взятой посылки или взять посылку более одного раза. Этот тип можно решить с помощью подхода динамического программирования.
Алгоритм задачи дробного рюкзака. Этот тип можно решить с помощью жадной стратегии.

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

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

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

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

Находите решения мельчайших подзадач.
Узнайте формулу (или правило) построения решения подзадачи путем решения даже самых маленьких подзадач.
Создайте таблицу, в которой хранятся решения подзадач. Затем вычислите решение подзадачи по найденной формуле и сохраните в таблицу.
Из решенных подзадач вы найдете решение исходной задачи.

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

Анализируя задачу о рюкзаке 0/1 с помощью динамического программирования, вы можете обнаружить несколько заметных моментов. Ценность алгоритма ранца зависит от двух факторов:

Сколько пакетов рассматривается
Оставшийся вес, который может поместиться в рюкзаке.

Таким образом, у вас есть две переменные величины.

Благодаря динамическому программированию вы получаете полезную информацию:

целевая функция будет зависеть от двух переменных величин
таблица вариантов будет двумерной.

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

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

Например: B[4][10] = 8. Это означает, что в оптимальном случае общий вес выбранных пакетов равен 8, когда на выбор есть 4 первых пакета (с 1-го по 4-й пакет) и максимальный вес рюкзака – 10. Не обязательно выбирать все 4 предмета.

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

Ввод, вы определяете:

W[i], V[i] — это, в свою очередь, вес и ценность посылки i, в которой i {1, …, n}.
М – максимальный вес, который может нести рюкзак.

В случае, если вам просто нужно выбрать только 1 пакет. Вы рассчитываете B[1][j] для каждого j: что означает максимальный вес рюкзака ≥ веса 1-го пакета.

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

С пределом веса j оптимальные выборы среди пакетов {1, 2, …, i – 1, i}, имеющие наибольшее значение, будут иметь две возможности:

Если пакет i не выбран, B[i][j] представляет собой максимально возможное значение при выборе среди пакетов {1, 2, …, i – 1} с пределом веса j. У вас есть:

B[i][j] = B[i – 1][j]

Если выбран пакет i (конечно, рассматриваем этот случай только тогда, когда W[i] ≤ j), тогда B[i][j] равно значению V[i] пакета i плюс максимальное значение, которое можно получить, выбрав один из пакеты {1, 2, …, i – 1} с лимитом веса (j – W[i]). То есть, с точки зрения ценности, которую вы имеете:

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

Из-за создания B[i][j], которое является максимально возможным значением, B[i][j] будет максимальным из двух вышеуказанных значений.

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

Итак, вам придется подумать, лучше ли выбрать пакет i или нет. Отсюда у вас есть рекурсивная формула следующего вида:

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

Легко увидеть B[0][j] = максимально возможное значение, выбрав из 0 пакет = 0.

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

Вы строите таблицу вариантов на основе приведенной выше рекурсивной формулы. Чтобы проверить правильность результатов (если не совсем, вы перестраиваете целевую функцию B[i][j]). Посредством создания целевой функции B[i][j] и таблицы вариантов вы сориентируете трассировку.

Таблица вариантов Б включает n+1 строк, M+1 столбцов,

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

Рассчитать таблицу вариантов — Таблица опций

Прослеживать

При расчете таблицы вариантов вас интересует B[n][M] — максимальное значение, полученное при выборе во всех n пакетах с лимитом веса M.

If Б[n][М] = Б[n – 1][М] тогда пакет n не выбран, вы отслеживаете B[n – 1][M].
If Б[n][М] ≠ Б[n – 1][М], вы заметите, что оптимальный выбор имеет пакет n и трассу B[n – 1][M – W[n]].

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

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

Примечание. Если B[i][j] = B[i – 1][j], пакет i не выбирается. B[n][W] – оптимальная суммарная стоимость упаковки, помещаемой в рюкзак.

Шаги по отслеживанию:

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

Java Code

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: ");
	
	while (n != 0) {
		if (B[n][M] != B[n - 1][M]) {
			System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
			
			M = M - W[n-1];
		}
		
		n--;
	}
}

Пояснение кода рюкзака:

Создайте таблицу B[][]. Установите значение по умолчанию для каждой ячейки — 0.
Постройте таблицу B[][] снизу вверх. Рассчитайте таблицу вариантов с помощью формулы поиска.
Вычислите B[i][j]. Если вы не выберете пакет i.
Затем оцените: если вы выберете пакет i, это будет более выгодно, чем сброс B[i][j].
Проследите таблицу от строки n до строки 0.
Если вы выберете пакет n. После выбора пакета n можно добавить только вес M – W[n – 1].

В этом уроке у вас есть два примера. Вот Java-код для запуска вышеуказанной программы с двумя примерами:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	//int W[] = new int[]{3, 4, 5, 9, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
	//int V[] = new int[]{3, 4, 4, 10, 4};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
	//int M = 11;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	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