Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut 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.

  2. #2
    Membre habitué
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    197
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 197
    Points : 143
    Points
    143

    Par défaut

    Comment pourrais-tu coder un algorithme quel qu'il soit si tu n'es pas capable de poser un test de dépassement ?
    Savoir pour comprendre et vice versa.

  3. #3
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    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 ?

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 676
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 676
    Points : 165 714
    Points
    165 714

    Par défaut



    À 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...
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    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

  6. #6
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 676
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 676
    Points : 165 714
    Points
    165 714

    Par défaut

    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.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  7. #7
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    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

  8. #8
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 676
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 676
    Points : 165 714
    Points
    165 714

    Par défaut

    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).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  9. #9
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    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

  10. #10
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    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

  11. #11
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 910
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 910
    Points : 4 781
    Points
    4 781

    Par défaut

    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  12. #12
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    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.

  13. #13
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 910
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 910
    Points : 4 781
    Points
    4 781

    Par défaut

    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  14. #14
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 676
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 676
    Points : 165 714
    Points
    165 714

    Par défaut

    Citation Envoyé par anapurna Voir le message
    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.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  15. #15
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    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 ?

  16. #16
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 676
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 676
    Points : 165 714
    Points
    165 714

    Par défaut

    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.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  17. #17
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    Voici mon code, pouvez-vous me donner votre avis dessus :
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  18. #18
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2015
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2015
    Messages : 44
    Points : 11
    Points
    11

    Par défaut

    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.

Discussions similaires

  1. Réponses: 2
    Dernier message: 24/02/2010, 23h08
  2. Compréhension d'un algorithme sur le problème du sac à dos
    Par Treuze dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 18/12/2006, 15h26

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo