Exercice 7 - Sac-à-dos

Nous souhaitons résoudre le problème du sac à dos par énumération exhaustive des solutions, c'est à dire comme des boeufs. Nous représenterons une solution $s$ (réalisable ou non) par la liste chaînée des indices des objets sélectionnés dans $s$. Nous représenterons une instance $i$ par deux tableaux $p$ (poids des objets) et $v$ (valeurs des objets). Une solution sera la liste chaînée des indices des objets placés dans le sac. Ecrivez les corps des sous-programmes suivants :

1. void* linkedListCopy(void* l). Copie les maillons de la liste chaînée l, mais pas les valeurs pointées par les maillons. Vous utiliserez linkedListMap.
2. Ecrivez le sous-programme void knapSackPrintSolution(linkedList* l), affiche la liste des indices formant la solution l, vous utiliserez linkedListApply.
3. Ecrivez un sous-programme linkedList* parties(linkedList* l), ce sous-programme prend en paramètre un ensemble représenté par une liste chaînée et retourne une liste chaînée dans laquelle chaque maillon est une liste chaînée contenant une partie de $l$. Vous utiliserez linkedListApply.
4. void knapSackPrintParties(linkedList* l), affiche toutes les parties de l, vous utiliserez linkedListApply.
5. void knapSackDestroyParties(linkedList* l) détruit l et les listes chaînées pointées par chaque maillon de cette liste.

Nous représenterons une instance du problème sac à dos avec une variable du type :

Ecrivez les corps des sous-programmes suivants :

1. knapSack* knapSackMake(long nbItems, long maxWeight), alloue la mémoire pour contenir l'instance ainsi que les deux tableaux.
2. void knapSackSetItem(knapSack* k, long index, long value, long weight), fixe les poids (weight) et valeur (value) de l'objet d'indice i de l'instance k.
3. long knapSackValue(knapSack* instance, linkedList* solution), retourne la somme des valeurs des objets de instance dont les indices sont dans la liste solution. Vous utiliserez la fonction linkedListApply.
4. long knapSackWeight(knapSack* instance, linkedList* solution), retourne le poids de la solution solution relative à l'instance instance. Vous procéderez de la même façon que dans la question précédente.
5. int knapSackIsFeasible(knapSack* instance, linkedList* solution), retourne vrai si est seulement si la solution solution relative à l'instance instance est réalisable.
6. void knapSackPrintInstance(knapSack* k), affiche la liste des poids des des valeurs de tous les objets de l'instance k. Par exemple,

   (i =   0, v =   1, w =   1)
   (i =   1, v =   2, w =   2)
   (i =   2, v =   9, w =   7)
   (i =   3, v =   8, w =   2)
   (i =   4, v =   5, w =   7)
   (i =   5, v =   6, w =   6)
   (i =   6, v =   7, w =   7)
   (i =   7, v =   4, w =   2)
   (i =   8, v =   3, w =   7)
   (i =   9, v =  10, w =   2)
   (i =  10, v =   1, w =   1)
   (i =  11, v =   2, w =   2)
   (i =  12, v =   9, w =   7)
   (i =  13, v =   8, w =   2)
   (i =  14, v =   5, w =   7)
   (i =  15, v =   6, w =   6)
   (i =  16, v =   7, w =   7)
   (i =  17, v =   4, w =   2)
   (i =  18, v =   3, w =   7)
   (i =  19, v =  10, w =   2)
   (i =  20, v =   1, w =   1)
   

7. void knapSackDestroy(knapSack* k), vous avez vraiment besoin que je vous donne des indications ?
8. linkedList* knapSackListInit(long n), retourne une liste chaînée contenant les éléments $\{1, \ldots, n\}$. Vous l'implémenterez de façon récursive.
9. linkedList* knapSackBruteForceSolve(knapSack* k) retourne la liste chaînée contenant la liste des indices des objets formant la solution optimale du problème k.
10. Jusqu'à quelle valeur de $n$ parvenez-vous à résoudre le problème ?
11. Montrez que le temps d'exécution est proportionnel au nombre de maillons crées, toutes listes confondues.
12. Evaluez le nombre de maillons en fonction de $n$, donnez la complexité de la résolution de knapsack par énumération de toutes les solutions.
13. Est-ce que cela vous explique pourquoi l'exécution est si longue ?