Implémentation des problèmes de sac à dos en Java

1. Introduction

Le problème du sac à dos est un problème d'optimisation combinatoire qui a de nombreuses applications. Dans ce tutoriel, nous allons résoudre ce problème en Java.

2. Le problème du sac à dos

Dans le problème du sac à dos, nous avons un ensemble d'articles. Chaque article a un poids et une valeur:

Nous voulons mettre ces articles dans un sac à dos. Cependant, il a une limite de poids:

Par conséquent, nous devons choisir les articles dont le poids total ne dépasse pas la limite de poids et leur valeur totale est aussi élevée que possible. Par exemple, la meilleure solution pour l'exemple ci-dessus est de choisir l'article de 5 kg et l'article de 6 kg, ce qui donne une valeur maximale de 40 $ dans la limite de poids.

Le problème du sac à dos a plusieurs variantes. Dans ce tutoriel, nous nous concentrerons sur le problème du sac à dos 0-1. Dans le problème du sac à dos 0-1, chaque article doit être choisi ou laissé pour compte. Nous ne pouvons pas prendre un montant partiel d'un article. De plus, nous ne pouvons pas prendre un article plusieurs fois.

3. Définition mathématique

Formalisons maintenant le problème du sac à dos 0-1 en notation mathématique. Étant donné un ensemble de n éléments et la limite de poids W , nous pouvons définir le problème d'optimisation comme:

Ce problème est NP-difficile. Par conséquent, il n'y a pas d'algorithme en temps polynomial pour le résoudre actuellement. Cependant, il existe un algorithme de temps pseudo-polynomial utilisant la programmation dynamique pour ce problème.

4. Solution récursive

Nous pouvons utiliser une formule de récursivité pour résoudre ce problème:

Dans cette formule, M (n, w) est la solution optimale pour n articles avec une limite de poids w . C'est le maximum des deux valeurs suivantes:

  • La solution optimale à partir de (n-1) éléments avec la limite de poids w (à l'exclusion du n- ième élément)
  • Valeur du n- ième élément plus la solution optimale à partir de (n-1) éléments et w moins le poids du n- ème élément (y compris le n- ème élément)

Si le poids du n -ième article est supérieur à la limite de poids actuelle, nous ne l'incluons pas. C'est donc dans la première catégorie des deux cas ci-dessus.

Nous pouvons implémenter cette formule de récursivité en Java:

int knapsackRec(int[] w, int[] v, int n, int W) { if (n  W) { return knapsackRec(w, v, n - 1, W); } else { return Math.max(knapsackRec(w, v, n - 1, W), v[n - 1] + knapsackRec(w, v, n - 1, W - w[n - 1])); } } 

Dans chaque étape de récursivité, nous devons évaluer deux solutions sous-optimales. Par conséquent, le temps d'exécution de cette solution récursive est O (2n).

5. Solution de programmation dynamique

La programmation dynamique est une stratégie pour linéariser des problèmes de programmation autrement exponentiellement difficiles. L'idée est de stocker les résultats des sous-problèmes afin de ne pas avoir à les recalculer ultérieurement.

Nous pouvons également résoudre le problème du sac à dos 0-1 avec une programmation dynamique. Pour utiliser la programmation dynamique, nous créons d' abord une table 2 dimensions avec des dimensions de 0 à n et 0 à W . Ensuite, nous utilisons une approche ascendante pour calculer la solution optimale avec ce tableau:

int knapsackDP(int[] w, int[] v, int n, int W) { if (n <= 0 || W <= 0) { return 0; } int[][] m = new int[n + 1][W + 1]; for (int j = 0; j <= W; j++) { m[0][j] = 0; } for (int i = 1; i <= n; i++) { for (int j = 1; j  j) { m[i][j] = m[i - 1][j]; } else { m[i][j] = Math.max( m[i - 1][j], m[i - 1][j - w[i - 1]] + v[i - 1]); } } } return m[n][W]; } 

Dans cette solution, nous avons une boucle imbriquée sur le nombre élément n et la limite de poids W . Par conséquent, son temps d'exécution est O (nW) .

6. Conclusion

Dans ce tutoriel, nous avons montré une définition mathématique du problème du sac à dos 0-1. Ensuite, nous avons fourni une solution récursive à ce problème avec l'implémentation Java. Enfin, nous avons utilisé la programmation dynamique pour résoudre ce problème.

Comme toujours, le code source de l'article est disponible à l'adresse over sur GitHub.