Résolution d'un problème de sac à dos 0/1 à l'aide d'un exemple de programmation dynamique

Quel est le problème du sac à dos ?

Problème de sac à dos L'algorithme est un problème très utile en combinatoire. Dans le supermarché il y a n colis (n ≤ 100) le colis i a un poids W[i] ≤ 100 et une valeur V[i] ≤ 100. Un voleur entre par effraction dans le supermarché, le voleur ne peut pas transporter un poids supérieur à M (M ≤ 100 ). Le problème à résoudre ici est le suivant : quels paquets le voleur emportera-t-il pour obtenir la valeur la plus élevée ?

Contribution:

  • Poids maximum M et nombre de colis n.
  • Tableau de poids W[i] et valeur correspondante V[i].

Sortie :

  • Maximisez la valeur et le poids correspondant en capacité.
  • Quels paquets le voleur emportera.

L’algorithme Knapsack peut être divisé en deux types :

  • Le problème 0/1 Knapsack utilisant la programmation dynamique. Dans ce type d'algorithme Knapsack, chaque paquet peut être pris ou non. En outre, le voleur ne peut pas prendre une fraction d’un colis saisi ni prendre un colis plus d’une fois. Ce type peut être résolu par une approche de programmation dynamique.
  • Algorithme du problème Fractional Knapsack. Ce type peut être résolu par Greedy Strategy.

Comment résoudre le problème du sac à dos à l'aide de la programmation dynamique avec un exemple

Dans la stratégie diviser pour régner, vous divisez le problème à résoudre en sous-problèmes. Les sous-problèmes sont ensuite divisés en sous-problèmes plus petits. Cette tâche se poursuivra jusqu'à ce que vous obteniez des sous-problèmes pouvant être résolus facilement. Cependant, au cours d’une telle division, vous risquez de rencontrer le même problème plusieurs fois.

L'idée de base de la programmation dynamique Knapsack est d'utiliser un tableau pour stocker les solutions des sous-problèmes résolus. Si vous êtes à nouveau confronté à un sous-problème, il vous suffit de prendre la solution dans le tableau sans avoir à le résoudre à nouveau. Les algorithmes conçus par programmation dynamique sont donc très efficaces.

Résoudre le problème du sac à dos à l'aide de la programmation dynamique

Pour résoudre un problème par programmation dynamique, vous devez procéder comme suitwing Tâches:

  • Trouver des solutions aux plus petits sous-problèmes.
  • Découvrez la formule (ou la règle) pour construire une solution de sous-problème grâce à des solutions même aux plus petits sous-problèmes.
  • Créez un tableau qui stocke les solutions des sous-problèmes. Calculez ensuite la solution du sous-problème selon la formule trouvée et enregistrez-la dans le tableau.
  • A partir des sous-problèmes résolus, vous trouvez la solution du problème initial.

Analysez le problème du sac à dos 0/1

Lors de l’analyse du problème 0/1 Knapsack à l’aide de la programmation dynamique, vous pouvez trouver quelques points notables. La valeur de l'algorithme du sac à dos dépend de deux facteurs :

  1. Combien de forfaits sont envisagés
  2. Le poids restant que le sac à dos peut stocker.

Vous disposez donc de deux quantités variables.

Avec la programmation dynamique, vous disposez d’informations utiles :

  1. la fonction objectif dépendra de deux quantités variables
  2. le tableau des options sera un tableau en 2 dimensions.

Si l'appel de B[i][j] est la valeur maximale possible en sélectionnant dans les packages {1, 2, …, i} avec limite de poids j.

  • La valeur maximale lorsqu'elle est sélectionnée dans n colis avec la limite de poids M est B[n][M]. En d’autres termes : lorsqu’il y a i colis à choisir, B[i][j] est le poids optimal lorsque le poids maximum du sac à dos est j.
  • Le poids optimal est toujours inférieur ou égal au poids maximum : B[i][j] ≤ j.

Par exemple : B[4][10] = 8. Cela signifie que dans le cas optimal, le poids total des colis sélectionnés est de 8, lorsqu'il y a 4 premiers colis à choisir (1er au 4ème colis) et le poids maximum du sac à dos est de 10. Il n’est pas nécessaire que les 4 éléments soient sélectionnés.

Formule pour calculer B[i][j]

En entrée, vous définissez :

  • W[i], V[i] sont à leur tour le poids et la valeur du colis i, dans lequel i Formule pour calculer B[i][j]{1, …, n}.
  • M est le poids maximum que peut supporter le sac à dos.

Dans le cas où vous n’avez qu’un seul forfait à choisir. Vous calculez B[1][j] pour chaque j : ce qui signifie que le poids maximum du sac à dos ≥ le poids du 1er colis

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

Avec la limite de poids j, les sélections optimales parmi les colis {1, 2, …, i – 1, i} pour avoir la plus grande valeur auront deux possibilités :

  • Si le colis i n'est pas sélectionné, B[i][j] est la valeur maximale possible en sélectionnant parmi les colis {1, 2, …, i – 1} avec une limite de poids de j. Tu as:
B[i][j] = B[i – 1][j]
  • Si le package i est sélectionné (bien sûr, ne considérez ce cas que lorsque W[i] ≤ j) alors B[i][j] est égal à la valeur V[i] du package i plus la valeur maximale peut être obtenue en sélectionnant parmi colis {1, 2, …, i – 1} avec limite de poids (j – W[i]). Autrement dit, en termes de valeur que vous avez :
B[i][j] = V[i] + B[i – 1][j – W[i]]

En raison de la création de B[i][j], qui est la valeur maximale possible, B[i][j] sera le maximum des 2 valeurs ci-dessus.

Base de la programmation dynamique

Vous devez donc vous demander s’il est préférable de choisir le forfait i ou non. De là, vous obtenez la formule récursive suivante :

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

Il est facile de voir B[0][j] = valeur maximale possible en sélectionnant parmi 0 package = 0.

Calculer le tableau des options

Vous créez un tableau d'options basé sur la formule récursive ci-dessus. Pour vérifier si les résultats sont corrects (sinon exactement, vous reconstruisez la fonction objectif B[i][j]). Grâce à la création de la fonction objectif B[i][j] et du tableau des options, vous orienterez le tracé.

Le tableau des options B comprend n+1 lignes, M+1 colonnes,

  • Tout d'abord, rempli des bases de la programmation dynamique : la ligne 0 comprend tous les zéros.
  • À l'aide de formules récursives, utilisez la ligne 0 pour calculer la ligne 1, utilisez la ligne 1 pour calculer la ligne 2, etc.… jusqu'à ce que toutes les lignes soient calculées.
Calculer le tableau des options
Tableau des options

Tracer

Lors du calcul du tableau des options, vous êtes intéressé par B[n][M] qui est la valeur maximale obtenue lors de la sélection dans les n colis avec la limite de poids M.

  • If B[n][M] = B[n – 1][M] alors le package n n'est pas sélectionné, vous tracez B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M], vous remarquez que la sélection optimale a le package n et la trace B[n – 1][M – W[n]].

Continuez à tracer jusqu'à atteindre la ligne 0 du tableau des options.

Algorithme pour consulter le tableau des options pour trouver les packages sélectionnés

Remarque : Si B[i][j] = B[i – 1][j], le package i n'est pas sélectionné. B[n][W] est la valeur totale optimale du colis mis dans le sac à dos.

Étapes de traçage :

  • Étape 1: À partir de i = n, j = M.
  • Étape 2: Regardez dans la colonne j, de haut en bas, vous trouvez la ligne i telle que B[i][j] > B[i – 1][j]. Marquer le package sélectionné i : Sélectionnez [i] = true ;
  • Étape 3: j = B[i][j] – W[i]. Si j > 0, passez à l'étape 2, sinon passez à l'étape 4
  • Étape 4: Basé sur le tableau des options pour imprimer les packages sélectionnés.

Code 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--;
	}
}
Fonction sac à dosDyProg() en Java

Fonction sac à dosDyProg() en Java

Explication du code Knapsack :

  1. Créer le tableau B[][]. Définir la valeur par défaut pour chaque cellule est 0.
  2. Construisez le tableau B[][] de manière ascendante. Calculez le tableau des options avec la formule de récupération.
  3. Calculer B[i][j]. Si vous ne sélectionnez pas le package i.
  4. Ensuite, évaluez : si vous sélectionnez le package i, ce sera plus avantageux que de réinitialiser B[i][j].
  5. Tracez le tableau de la ligne n à la ligne 0.
  6. Si vous choisissez le forfait n. Une fois sélectionné le package n, vous ne pouvez ajouter que le poids M – W[n – 1].


Dans ce didacticiel, vous avez deux exemples. Voici le code Java pour exécuter le programme ci-dessus avec deux exemples :

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);
}

Vous avez le résultat :

  • Premier exemple :
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
  • Deuxième exemple :
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