Programmation dynamique pour le probleme du sac a dos

Version imprimable

Bonjour,

Je travaille actuellement sur le probleme du sac a dos et j ai vu dans la litterature qu il y a deux approches de programmation dynamique pour le resoudre de facon exacte (parmi d autres) : une sequentielle et une recursive.

Mais je n ai pas trop compris la difference entre ces deux approches et laquelle est la plus efficace ?

Pourriez vous m en donner plus de details svp ?

P.S. J ai implemente une premiere version (tres basique) du sac a dos dont voici le code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
int n = 4;
 
Float[] values = new Float[n + 1];
int[] weights = new int[n + 1];
 
    values[1] = 5f;
    values[2] = 3f;
    values[3] = 2f;
    values[4] = 1f;
    weights[1] = 3;
    weights[2] = 2;
    weights[3] = 1;
    weights[4] = 4;
 
    int C = 8;
 
    Float[][] tab = new Float[C + 1][n + 1];
 
    for(int v = 0; v <= C; v++) {
      tab[v][0] = 0f;
    }
 
    for(int i = 1; i <= n; i++) {
      for(int v = 0; v <= C; v++) {
        if(v < weights[i]) {
          tab[v][i] = tab[v][i - 1];
        }
        else {
          tab[v][i] = Math.max(tab[v][i - 1], tab[v - weights[i]][i - 1] + values[i]);
        }
      }
    }
 
    System.out.println("Valeur optimale " + tab[C][n]);
 
    int[] x = new int[n + 1];
 
    for(int i = 1; i <= n; i++) {
      x[i] = 0;
    }
 
    int k = n;
    while(C > 0 && k > 0) {
      if(!tab[C][k].equals(tab[C][k - 1])) {
        x[k] = x[k] + 1;
        C = C - weights[k];
      }
      k--;
    }
 
    System.out.println("Selected Objects : ");
 
    for(int j = 1; j <= n; j++) {
      if(x[j] == 1) {
        System.out.println("Object " + j + " Value " + values[j]);
      }
    }

merci de votre aide.

Bonjour,

En premier lieu, évite de supposer que les gens connaissent le problème dont tu parle. (Wikipédia : problème du sac à dos)

En suite pour ce qui est du code :
1. On nomme ses variables correctement.
Car actuellement, je ne sais absolument pas ce que fait ton algorithme.

Code:

1
2
3
4
5
    int[] x = new int[n + 1];
 
    for(int i = 1; i <= n; i++) {
      x[i] = 0;
    }

L'initialisation de l'ensemble des colonnes à 0 n'est pas nécessaire pour les types primitifs. En effet, le tableau est remplit par la valeur par défaut (ie 0).
Cela est nécessaire pour les objets car la valeur par défaut est null pour ceux-ci

Code:

1
2
3
4
5
Float[] values = new Float[n + 1];
values[1] = 5f;
values[2] = 3f;
values[3] = 2f;
values[4] = 1f;

Il est dommageable d'utiliser un tableau d'objet Float, alors que tu utilise le type primitif float.

Voici ton code après quelques modiciations :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
		int nombreObjet = 4;
 
		float[] values = new float[nombreObjet + 1];
		int[] weights = new int[nombreObjet + 1];
 
		values[1] = 5f;
		values[2] = 3f;
		values[3] = 2f;
		values[4] = 1f;
		weights[1] = 3;
		weights[2] = 2;
		weights[3] = 1;
		weights[4] = 4;
 
		int poidsDisponibleRestant = 8;
 
		float[][] tab = new float[poidsDisponibleRestant + 1][nombreObjet + 1];
 
		for (int i = 1; i <= nombreObjet; i++) {
			for (int v = 0; v <= poidsDisponibleRestant; v++) {
				if (v < weights[i]) {
					tab[v][i] = tab[v][i - 1];
				} else {
					tab[v][i] = Math.max(tab[v][i - 1],
							tab[v - weights[i]][i - 1] + values[i]);
				}
			}
		}
 
		System.out.println("Valeur optimale " + tab[poidsDisponibleRestant][nombreObjet]);
 
		int[] sac = new int[nombreObjet + 1];
 
		int k = nombreObjet;
		while (poidsDisponibleRestant > 0 && k > 0) {
			if (tab[poidsDisponibleRestant][k] != tab[poidsDisponibleRestant][k - 1]) {
				sac[k] = sac[k] + 1;
				poidsDisponibleRestant = poidsDisponibleRestant - weights[k];
			}
			k--;
		}
 
		System.out.println("Selected Objects : ");
 
		for (int j = 1; j <= nombreObjet; j++) {
			if (sac[j] == 1) {
				System.out.println("Object " + j + " Value " + values[j]);
			}
		}

Voici une version du même algorithme utilisant le principe de programmation objet de Java :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
public class MonObjet {
 
	private float poids = 0;
	private int valeur = 0;
 
	public MonObjet(int valeur, float poids) {
		this.valeur = valeur;
		this.poids = poids;
	}
 
	public float getPoids() {
		return poids;
	}
 
	public int getValeur() {
		return valeur;
	}
 
	public float getRapport(){
		if(poids <= 0){
			throw new RuntimeException("Objet n'ayant pas de poids.");
		}
		return valeur/poids;
	}
 
	public static class MonComparateur implements Comparator<MonObjet> {
 
		@Override
		public int compare(MonObjet o1, MonObjet o2) {
			if(o1.getRapport() < o2.getRapport()){
				return 1;
			}
			if (o1.getRapport() > o2.getRapport()){
				return -1;
			}
			return 0;
		}
 
	}
	public static void main(String[] args) {
		//Je déclare le poids maximum du sac
		float poidsMax = 5;
		// Je déclare la liste d'objet disponible
		List<MonObjet> listObjet = new ArrayList<MonObjet>();
		listObjet.add(new MonObjet(5, 3));
		listObjet.add(new MonObjet(1,4));
		listObjet.add(new MonObjet(3, 2));
		listObjet.add(new MonObjet(2, 1));
		// Je trie la liste du plus remtable au moins rentable.
		Collections.sort(listObjet, new MonComparateur());
		// J'affiche les rapports pour vérifier l'état de ma liste
		System.out.println("Voici la liste d'objet que j'ai à ma disposition");
		afficheMaListe(listObjet);
 
		// Je déclare le poids disponible du sac
		float poidsDisponible = poidsMax;
		// Je déclare ma liste représentant mon sac
		List<MonObjet> monSac = new ArrayList<MonObjet>();
		for (MonObjet monObjet : listObjet) {
			//Si l'objet rentre, je l'ajoute
			if(poidsDisponible> monObjet.getPoids()){
				poidsDisponible -= monObjet.getPoids();
				monSac.add(monObjet);
			}
		}
		// J'affiche les rapports pour vérifier l'état de ma liste
		System.out.println("Voici la liste d'objet que j'ai pris dans mon sac");
		afficheMaListe(monSac);
	}
 
	private static void afficheMaListe(List<MonObjet> listObjet) {
		for (MonObjet monObjet : listObjet) {
			System.out.println("("+monObjet.getValeur()+","+monObjet.getPoids()+") => "+monObjet.getRapport());
		}
	}
}

Il n'y a pas d'approche récursive dans ton code. Cela implique qu'une méthode/fonction s'appelle elle-même.
Wikipédia : Algorithme récursif
L'algorithme peut-être considéré comme séquentiel. Du fait qu'on mémorise le poids disponible. Mais seulement si on considère cela au niveau du traitement d'un objet.

Wikipédia : Logique séquentielle

Cordialement,
Patrick Kolodziejczyk.

Citation:

Envoyé par ahmadou_20

P.S. J ai implemente une premiere version du sac a dos et je ne suis meme pas sur si s agit d une approche recursive ou sequentielle !!

Avant tout il faut revoir la définition de la programmation séquentielle et récursive.

La programmation séquentielle, c'est l'approche "classique" d'un programme, une suite d'instruction avec des boucles, des branchements conditionnelles (if)....

La programmation récursive, c'est en plus de la suite d'instruction, c'est de pouvoir s'appeler soit même.

Typiquement, si tu veux calculer la somme des n premiers entiers,l'approche séquentielle va mettre en oeuvre une boucle, alors que dans l'approche récursive, tu vas calculer la somme des n-1 premiers entiers et y ajouter n :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int sommeIterative(int n) { int somme = 0; for(int i = 0; i <= n ; i++) { somme += i; } return somme; } public int sommeRecursive(int n) { if (n = 0) { return 0; } else { return n + sommeRecursive(n - 1); } }
As toi d'en déduire l'approche que tu as utilisée !

27/08/2014, 10h51
benratti

Citation:

Envoyé par kolodz

En premier lieu, évite de supposer que les gens connaissent le problème dont tu parle. (Wikipédia : problème du sac à dos)

hum, le problème du sac à dos est tout de même extrêmement connu et et même un problème de base en algorithmique. C'est un peu comme si quelqu'un demande de l'aide sur l'implémentation d'un quick-sort et que tu lui demandais de présenter le quick-sort.
27/08/2014, 11h00
ahmadou_20

D accord merci pour toutes vos precisions (et remarques concerant la lisibilite du code : @kolodz).

En fait j ai essaye de chercher sur internet le principe de la programmation dynamique recursive pour le probleme du sac a dos. Mais je n ai pas trouve quelque chose de vraiment tres pertinent.

Auriez vous une idee sur cette approche (meme en pseudo code) ?

Merci bcp encore une fois pour votre aide !!!
27/08/2014, 11h02
benratti

Citation:

Envoyé par ahmadou_20

Mais je n ai pas trop compris la difference entre ces deux approches et laquelle est la plus efficace ?

Je dirais aucune. Le problème du sac à doc est NP-Complet, donc en simplifié, qu'il ne se resout pas de manière efficace car c'est un problème connu pour être complexe!
27/08/2014, 11h53
kolodz

Citation:

Envoyé par benratti

hum, le problème du sac à dos est tout de même extrêmement connu et et même un problème de base en algorithmique.

Nous somme dans la section Débuter Java et non dans la section Expert Algorithme. Les principaux intéressé de cette section sont des personnes n'ayant peu ou pas de compétence de le domaine.
Il est peu probable qu' ahmadou_20 ai une connaissance de ce problème de base avant de vouloir l'implémenté. Du coup, toutes autres personnes de son niveau lisant son sujet n'aura pas connaissance de ce qu'il veut réaliser. Or il est important que toutes les personnes du forum soient capable d'aider à son niveau.

Citation:

Envoyé par benratti

C'est un peu comme si quelqu'un demande de l'aide sur l'implémentation d'un quick-sort et que tu lui demandais de présenter le quick-sort.

Pour le coup, le cas c'est déjà présenté. J'ai justement poser la question... Et cela a beaucoup aidé !
L'important quand tu veux résoudre un problème, c'est de bien le comprendre !

L'un des cas où l’algorithme actuelle ne donne pas la bonne solution est :

Citation:

Sac de taille 100
Objets de (valeur, poids) :
(1.1, 51)
(1, 50)
(1, 50)

Cordialement,
Patrick Kolodziejczyk.