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

по: Сара Чен Сара Чен
Hours Обновено

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

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

Вход:

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

Изход:

  • Увеличете максимално стойността и съответното тегло в капацитета.
  • Кои опаковки крадецът ще отнесе.

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

  • Проблемът с раницата 0/1 с помощта на динамично програмиране. В този тип алгоритъм на раницата всеки пакет може да бъде взет или не. Освен това крадецът не може да вземе малка част от взет пакет или да вземе пакет повече от веднъж. Този тип може да бъде разрешен чрез подход на динамично програмиране.
  • Алгоритъм за дробна задача на раницата. Този тип може да бъде разрешен от Greedy Strategy.

Как да решите проблема с раницата с помощта на динамично програмиране с пример

В стратегията „разделяй и владей“ вие разделяте проблема, който трябва да бъде разрешен, на подпроблеми. Подпроблемите са допълнително разделени на по-малки подпроблеми. Тази задача ще продължи, докато получите подпроблеми, които могат да бъдат решени лесно. В процеса на такова разделяне обаче може да срещнете същия проблем много пъти.

Основната идея на динамичното програмиране на Knapsack е да се използва таблица за съхраняване на решенията на решените подпроблеми. Ако отново се сблъскате с подпроблем, просто трябва да вземете решението в таблицата, без да се налага да го решавате отново. Следователно алгоритмите, проектирани чрез динамично програмиране, са много ефективни.

Решете проблема с раницата с помощта на динамично програмиране

За да разрешите проблем чрез динамично програмиране, трябва да изпълните следните задачи:

  • Намерете решения на най-малките подпроблеми.
  • Открийте формулата (или правилото) за изграждане на решение на подпроблем чрез решения дори на най-малките подпроблеми.
  • Създайте таблица, която съхранява решенията на подзадачите. След това изчислете решението на подзадачата по намерената формула и запазете в таблицата.
  • От решените подзадачи намирате решението на първоначалния проблем.

Анализирайте проблема с раницата 0/1

Когато анализирате проблема с раницата 0/1 с помощта на динамично програмиране, можете да намерите някои забележими точки. Стойността на алгоритъма на раницата зависи от два фактора:

  1. Колко пакета се разглеждат
  2. Оставащото тегло, което може да побере раницата.

Следователно имате две променливи количества.

С динамичното програмиране имате полезна информация:

  1. целевата функция ще зависи от две променливи величини
  2. таблицата с опции ще бъде двуизмерна таблица.

Ако извикването на 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 Формула за изчисляване на B[i][j]{1, …, n}.
  • M е максималното тегло, което може да носи раницата.

В случай, че просто имате само 1 пакет за избор. Изчислявате B[1][j] за всяко j: което означава максималното тегло на раницата ≥ теглото на първия пакет

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] ще бъде максималната от горните 2 стойности.

Основи на динамичното програмиране

Така че трябва да помислите дали е по-добре да изберете пакет 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] и таблицата с опции ще ориентирате трасирането.

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

  • Първо, изпълнен с основата на динамичното програмиране: Ред 0 включва всички нули.
  • Използвайки рекурсивни формули, използвайте ред 0, за да изчислите ред 1, използвайте ред 1, за да изчислите ред 2 и т.н. … докато не бъдат изчислени всички редове.
Изчислете таблицата с опции
Таблица с опции

Следа

Когато изчислявате таблицата с опции, вие се интересувате от B[n][M], което е максималната стойност, получена при избор във всички n пакета с ограничение на теглото M.

  • If B[n][M] = B[n – 1][M] тогава пакет n не е избран, проследявате B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M], забелязвате, че оптималната селекция има пакет n и следа B[n – 1][M – W[n]].

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

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

Забележка: Ако B[i][j] = B[i – 1][j], пакетът i не е избран. B[n][W] е оптималната обща стойност на пакета, поставен в раницата.

Стъпки за проследяване:

  • Стъпка : Започвайки от i = n, j = M.
  • Стъпка : Погледнете в колона j, нагоре отдолу, намирате ред i, така че B[i][j] > B[i – 1][j]. Маркирайте избрания пакет i: Изберете [i] = true;
  • Стъпка : j = B[i][j] – W[i]. Ако j > 0, отидете на стъпка 2, в противен случай отидете на стъпка 4
  • Стъпка : Въз основа на таблицата с опции за отпечатване на избраните пакети.

Java код

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--;
	}
}
Функция napsackDyProg() в Java

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

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

  1. Създайте таблица B[][]. Задайте стойността по подразбиране за всяка клетка е 0.
  2. Изградете таблица B[][] по начин отдолу нагоре. Изчислете таблицата с опции с формулата за извличане.
  3. Изчислете B[i][j]. Ако не изберете пакет i.
  4. След това преценете: ако изберете пакет i, той ще бъде по-полезен от нулиране на B[i][j].
  5. Проследете таблицата от ред n до ред 0.
  6. Ако изберете пакет 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