import java.util.*; /* Question 1 : il y a 2^n (2 puissance n) candidats à être une solution. Plusieurs façons de voir la chose : - un candidat est une partie (sous-ensemble) de l'ensemble des n objets. Un ensemble à n éléments possède 2^n parties. - un candidat peut être codé par un mot de n bits (le bit 0 indiqué si l'objet 0 est dans le candidat, etc). Il y a 2^n mots différents de n bits. - les candidats sont : tous les sous-ensembles à 1 élément C(1,n), tous les sous-ensembles à 2 éléments C(2,n), etc) donc la somme_{0<i<=n} C(i,n), ce qui constitue la somme des éléments de la n-ième ligne du triangle de Pascal; La somme est égale à 2^n. - un candidat est une fonction qui à un objet, associe une valeur indiquant s'il est dans un candidat ou non. On a donc une fonction d'un ensemble à n éléments à valeur dans un ensemble à 2 élements. Il y a exactement 2^n fonctions différentes. Question 2: Pour répondre à la question 2, il suffit d'utiliser l'une des "visions" de la question 1 pour énumérer les candidats. Ce qui signifie qu'il faut choisir un ordre. On peut par exemple utiliser les mots de n-bits pour obtenir quelque chose comme (en version itérative) : public static void enumere(int N) { int sousEnsemble; // On génère tous les mots de N bits (tous les entiers sur N bits) for (sousEnsemble=1; sousEnsemble<(1<<N); sousEnsemble++) { verifie(sousEnsemble,N); } } public static void verifie(int candidat,N) { int p=0, v=0; // calculons le poids et volume du candidat for (int e=0; e<N; e++) { // l'élément e est dans le candidat if ( (1<<e)&candidat != 0) { p += poids[e]; v += volume[e]; } } // si le candidat rentre pile-poil on l'affiche! if (p==P && v==V) { afficheSolution(candidat); } } Note: Si cet exemple fonctionne, il n'est pas aisé de le modifier pour le backtracking de la question 4 (pourquoi ?) Une autre solution, récursive cette fois, pourrait être : public static int []t; public static int N; public static void doIt() { N = 5; t = new int[N]; enumeration_recursive(0,0); } public static void enumeration_recursive(int i,int l) { for (int j=i; j<N; j++) { t[i]=j; aff(l); enumeration_recursive(j+1,l+1); } } où aff(l) est une fonction qui teste et/ou affiche si le candidat (de longueur l) est acceptable ou non. Note: Il est plus facile de modifier cet exemple pour le backtracking de la question 4, comment ? pourquoi ? Question 3: À chaque noeud de l'arbre on associe le poids et volume courants remplis jusqu'ici, chaque arrête est étiquetée par l'objet que l'on rajoute pour essayer d'aller plus loin... Si on est allé trop loin, on n'insiste pas! On marque par -i,j- un calcul qui ne peut mener à une solution car l'un des critères est déjà dépassé... On ne doit pas dépasser P=3 et V=4 On marque par *i,j* une solution correcte. (p=0,v=0) | +--------------+-----+-----+-----------+---------+ | | | | | 0 1 2 3 4 | | | | | (2,3) (1,2) (2,1) (1,3) (2,2) | | | | +-------+--+--+ +-----+-----+ +-----+ 4 | | | | | | | | | 1 2 3 2 3 4 3 4 -3,5- | | | | | | | | -3,5- -4,4- -3,6- -3,3- -2,5- *3,4* *3,4* -4,3- On obtient donc que {1,4} et {2,3} sont des solutions. On notera que seulement 15 candidats auront été générés pour trouver TOUTES les solutions alors que la méthode exhaustive aurait nécessité le test de 2^5=32 candidats. Note: on coupe en -3,3- car si le poids est correct on sait qu'il n'existe pas d'objet de poids nul et donc que compléter ne servira à rien! Question 4: Le code suivant est une réponse à cette question. Attention, il était explicitement demandé d'utiliser une méthode récursive... L'idée ici est de générer les suites ordonnées partielles comme dans l'arbre ci-dessus. Si on est au point (a0,a1,a2,...a{k-1},ak) avec ai<aj lorsque i<j, il faut essayer récursivement avec un élément de plus (a0,a1,a2,...a{k-1},a{k},a{k}+1) puis en modifiant le dernier élément (a0,a1,a2,...a{k-1},a{k}+1) en se limitant bien entendu à k<=N et a{k}<=N On teste à chaque ensemble engendré s'il est solution ou non. La coupure de l'arbre est alors simple à obtenir, dès que l'une des sommes poids ou volume est plus grande que celle attendue, on arrête la récursion. */ public class Exo3 { // 0 1 2 3 4 5 6 7 8 910111213 static int[] poids = {2,9,1,3,2,5,3,2,1,4,7,3,5,1}; static int[] volume = {1,4,3,2,4,2,5,3,1,2,3,1,3,2}; static int[] objets; // On cherche à remplir un conteneur avec les caractéristiques P,V static int P = 15; static int V = 11; public static void afficherSolution(int n) { System.out.print("solution ["); for (int i=0; i<n; i++) System.out.print(objets[i]+","); System.out.print(objets[n]+"]"); // Pour vérifier que tout va bien, si on y croit pas... int t = 0; for (int i=0; i<=n; i++) t += poids[objets[i]]; System.out.print(" -> {"+t+","); t = 0; for (int i=0; i<=n; i++) t += volume[objets[i]]; System.out.println(t+"}"); } public static void afficherCandidat(int n) { System.out.print("["); for (int i=0; i<n; i++) System.out.print(objets[i]+","); System.out.println(objets[n]+"]"); } /* Un candidat est à chaque instant le contenu des "nombres" premiers éléments du tableau d'objets. */ public static void conteneur(int nombre, int next, int poidsActuel, int volumeActuel) { // On va trop loin... if (next==objets.length) return; // Ok essayons cet élément... objets[nombre] = next; // Pour observer ce qui se passe, où en est-on dans l'énumération ? afficherCandidat(nombre); // On a trouvé une solution if (poidsActuel+poids[next]==P && volumeActuel+volume[next]==V) afficherSolution(nombre); // Tout reste encore possible s'il y a de la place et que la limite // de poids n'est pas dépassée, alors essayons avec un élément de plus if (poidsActuel+poids[next]<P && volumeActuel+volume[next]<V) conteneur(nombre+1, next+1, poidsActuel+poids[next], volumeActuel+volume[next]); // Essayons un autre élément plutôt que celui-ci conteneur(nombre, next+1, poidsActuel, volumeActuel); } public static void main(String []args) { Scanner in = new Scanner(System.in); int n=0; do { System.out.println("Combien d'éléments [1,"+poids.length+"] ?"); n = in.nextInt(); } while (n<0 || n>14); objets = new int[n]; // On commence avec rien du tout conteneur(0,0,0,0); } }