Problème du sac à dos

Bonjour,

je voudrais coder un algorithme de résolution du problème du sac à dos. Cependant, pour qu'il corresponde à mon sujet, il faudrait je pense aborder un problème du sac à dos multidimensionnel. Cependant, comme ce problème est beaucoup plus contraignant qu'un simple problème du sac à dos, j'aimerais savoir s'il y avait des alternatives. Je vous présente ma situation : je cherche à maximiser la valeur total sans dépasser une limite de poids mais aussi sans dépasser un nombre limite d'objets à mettre dans le sac. La contrainte supplémentaire est donc le nombre limité d'objets cependant, comme est peut-être "plus simple" que d'autres contraintes du problème du sac à dos multidimensionnel, n'existe-t-il pas des alternatives basés sur le problème du sac à dos avec des vérifications de non dépassement du seuil d'objet dans l'algorithme.

J'espère avoir été assez clair.

Merci à tous pour votre aide qui, je n'en doute pas, me sera très utile pour la suite.

Comment pourrais-tu coder un algorithme quel qu'il soit si tu n'es pas capable de poser un test de dépassement ?

Le problème n'est pas de coder le test de dépassement mais il suffit de coder l'algorithme de résolution du problème du sac à dos simple et d'y ajouter ce test ou faut-il obligatoirement utilisé un algorithme du sac à dos multidimensionnel ?

:salut:

À ma connaissance, il n'existe pas de réduction du sac à doc multidimensionnel vers un sac à dos classique. Par contre, il existe des approches qui résolvent le problème multidimensionnel en n'utilisant que des sacs à dos classiques, comme https://homepages.laas.fr/elbaz/EJIE.pdf. Déjà, il faudrait savoir si tu cherches une solution exacte ou approchée au problème...

C'est pour un projet d'étude, si les solutions exactes sont trop complexes à obtenir, des solutions approchées iront très bien. Sinon, tu penses que pour avoir ma contrainte de nombre d'objet maximum en plus de la contrainte du poids on est obligé de passer par un problème multidimensionnel. On ne peut pas juste rajouter des lignes de test dans le problème classique ?
Merci beaucoup

Si, tu peux juste ajouter des tests, mais tu n'as alors aucune garantie d'obtenir une bonne solution (ni même une solution, je crains...). Pour avoir une solution réalisable à coup sûr, je te proposerais plutôt une heuristique gloutonne : tu tentes de placer les objets en commençant par celui qui apporte le plus de valeur par rapport à son utilisation (donc celui qui maximise le ratio entre la valeur et la somme des poids dans chaque dimension) jusqu'à remplir ton sac.

J'avais testé un algorithme glouton mais je n'étais pas sûr qu'il fonctionne correctement pour du multi-dimensionnel. Si on donne a chaque objet deux poids : un poids en kg et un poids valant 1 pour chaque objet. On va chercher à ne pas dépasser le nombre d'objets ni la charge du sac. Cependant, ma fonction de tri doit aussi prendre en compte le second poids comme il est commun à tous les objets ? Dans mon algorithme glouton actuel, je trie que par le rapport valeur / poids et dans mon algorithme de choix des objets, j'ai deux critères d'arrêt de la boucle : soit on sort de la liste des objets, soit on a dépassé la limite autorisée d'objet dans le sac. Est-ce satisfaisant ou j'ai fait une erreur de raisonnement ? De plus, pour mon projet, j'aurais aimé proposer différentes approches de la résolution du problème et les comparer entre elles (limites de chacune et qualité du résultat). Les approches génétiques et dynamiques (qui je pense constitue les principales approches) sont elles concevable pour mon problème à mon niveau ?
Merci beaucoup pour ton aide

Vu comme ça, je dirais que ton raisonnement est correct.

Pour ton cas, je pense plutôt à des algorithmes dynamiques (vois, par exemple, https://cs.stackexchange.com/questio...ic-programming) et par branchement (comme la première référence que je t'ai envoyée). Une petite implémentation comme un MILP ne devrait pas être compliquée à ajouter à ton jeu d'algorithmes ! Ou encore de la programmation par contraintes (https://pdfs.semanticscholar.org/401...de130744aa.pdf).

Je vais regarder tout ce que tu m'as envoyé, puis-je te recontacter ultérieurement en cas de (probable) problème.
Merci beaucoup pour ton expertise

Je me suis intéressé à la programmation dynamique. J'ai bien compris le concept ainsi que son utilisation pour résoudre un sac à dos classique. Cependant, je ne suis pas sûr de l'adaptation à ma situation. Dans le cas classique, on test si l'objet i peut aller ou non dans le sac en fonction de son poids et éventuellement on regarde le max des deux situations s'il peut y aller. Dans mon cas, je dois rajouter mon test sur le nombre d'objets avec celui du poids ? Si oui, on différencierai donc les cas suivants : l'objet i peut y aller (assez de place et de poids libre) puis on prend le max des valeurs comme dans le sac à dos classique ; l'objet i ne peut pas y aller (quel que soit la cause).
Merci beaucoup

salut

une approche bien plus simple peut fonctionner

L'objet a placer dans tes sac ou ensemble doit être défini de tels manière que
la somme des objet mis de cote est inférieur ou égale au seuil du nombre maxi d'objet voulu
et que la somme des poids doit être maximal mais inférieur ou égale au seuil de poids voulue

Prenons un exemple concret Nous avons 8 objets de poids divers
la première chose et de le trié par poids

9,9,6,6,6,4,3,2

la deuxième chose est de connaitre le nombre de sac que tu as besoin
disons que l'on veut max 3 objets par sac
(8 mod 3) +1= 3 donc on auras au minimum 3 sacs
ensuite on remplit les sacs avec les premiers poids forts
donc 9,9,6
imaginons que tes sacs doivent peser 12 maxi
le deuxieme tour pour chaque sac on essai de completer j'usquau 12
les éléments restant a distribuer étant 6,6,4,3,2

premier sac 9+6 > 12 c'est pas bon on passe a l’élément suivant
9+6 > 12 " "
9+4 > 12 " "
9+3 = 12 ....on le retient on passe au sac suivant
reste 6,6,4,2

deuxieme sac 9+6 > 12 c'est pas bon on passe a l’élément suivant
9+6 > 12 " "
9+4 > 12 " "
9+2 < 12 ....on le retient
reste 6,6,4
deuxieme sac 11+6 > 12 c'est pas bon on passe a l’élément suivant
11+6 > 12 " "
11+4 > 12 " "
on a fait le tour des éléments on passe au sac suivant

reste 6,6,4
Troisieme sac 6+6 = 12 ....on le retient on passe au sac suivant

reste 6,4
il ne reste plus de sac disponible
on calcul de nouveau le nombre de sacs que l'on pourrait avoir besoins
(nbrestant mod 3) +1 = 1
dans notre cas on creer 1 nouvau sac
6
reste 4
6+4 < 12 ....on le retient

toutes les valeur on été distribué on a fini

anapurna je pense que tu n'as pas compris ma situation. Je ne dispose pas de plusieurs sacs mais d'un seul et je ne souhaite pas mettre plus de n objets dedans sans dépasser la limite de poids et en maximisant la valeur.

salut

c'est encore plus simple alors
tu veux simplement maximiser le rendement de ton sac

dans ce cas là ce n'est même pas le problème du sac à dos qui lui s'occupe de la répartition d’élément dans de multiple récipient
cela ressemble plus a la recherche d'une valeur optimal c'est à dire à de la programmation linéaire que l'on se sert dans les calculs de stock

Citation:

---

Envoyé par anapurna

cela ressemble plus a la recherche d'une valeur optimal c'est à dire à de la programmation linéaire que l'on se sert dans les calculs de stock

---

Programmation linéaire… en nombres entiers, sinon, on en vient à mettre des demi-objets dans un sac ! Le problème du sac à dos est, de manière traditionnelle, défini pour un seul et unique récipient (enfin, chaque fois que j'en ai vu parler…).

Sinon, pour la programmation dynamique : pour le sac à dos classique, tu calcules une valeur x_ij en considérant les objets entre le 1 et le i, une capacité entre 1 et j ; à plusieurs dimensions, tu dois passer à un tableau à trois dimensions, x_ijk : objet 1 à i, première ressource entre 1 et j, deuxième ressource entre 1 et k. Pour itérer, tu te poses des questions comme : si je considère tel objet en plus à ressources constantes, puis-je augmenter la valeur totale ? Si j'augmente une ressource d'une unité, en gardant l'autre constante et sans considérer d'objet supplémentaire, puis-je augmenter la valeur totale ? Ce n'est pas exactement ce que tu expliques, mais ça en est proche.

Dans ma situation chaque objet a un poids, notons p_i, une valeur, v_i, et un poids constant à 1 pour tous les objets. Je cherche à maximiser la somme des v_i retenus, sous contraintes que la somme des p_i retenus soit <= W et que la somme des poids constants à 1 soit <= N. Du coup en programmation dynamique, je vais itérer sur les objets et sur les capacités mais je ne peux pas itérer sur la seconde dimension comme elle est constante et égale à 1. Je comprends l'intérêt de le faire en cas général pour un problème à 2 dimensions mais en ais-je besoin ?

Tous tes objets utilisent la même quantité de ressources, mais tu dois quand même itérer sur la capacité de ton sac pour chaque ressource.

Voici mon code, pouvez-vous me donner votre avis dessus :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

def dp(list_obj): KP = [[[0 for k in range(MAX_OBJ + 1)] for j in range(W + 1)] for i in range(len(list_obj) + 1)] for i in range(1, len(list_obj) + 1): w_i, v_i = list_obj[i - 1][0], list_obj[i - 1][1] for w in range(1, W + 1): for k in range(1, MAX_OBJ + 1): if w_i > w: KP[i][w][k] = KP[i - 1][w][k] elif i > k: KP[i][w][k] = max(KP[i - 1][w - w_i][k - 1] + v_i, KP[i - 1][w][k]) else: KP[i][w][k] = max(KP[i - 1][w - w_i][k] + v_i, KP[i - 1][w][k]) return KP

---

Bonjour,
je reviens vers vous pour une nouvelle question. J'ai fini la programmation dynamique et l'ai adapté pour retrouver le chemin utilisé. Cependant, il faut obligatoirement stocker un nouveau tableau de même taille pour ce faire ? N"existe-t-il pas d'optimisation en mémoire pour cette version ?
Par ailleurs, je suis actuellement sur l'algorithme génétique et j'ai pu coder toutes les fonctions intervenants dans l'algorithme. Cependant, j'ai une petite question. Quand j'ai ma population, j'en sélectionne la moitié pour la suite (croisements et mutations). Cependant, faut-il faire toutes les combinaisons de croisement possibles et garder les meilleurs ? A quel moment précis intervient la probabilité de croisement ? De plus, j'ai choisi (je ne sais pas si c'est judicieux) de faire comme mutation un échange d'un 0 et 1 dans mon codage binaire (pour être sûr qu'il respecte la limite d'objet maximum). Dans ce cas, la probabilité de mutation intervient dans le choix de faire muter un individu et non plus un caractère du code ?
Merci beaucoup pour votre aide.