Sac à dos multiple
Olympiades mathématiques, énigmes et défis
-
coinroad
- Membre Naturel
- Messages: 17
- Enregistré le: 22 Déc 2020, 04:31
-
par coinroad » 06 Mai 2023, 20:50
Dans le problème de sac à dos multiple, est il possible de faire varier le poids de chaque item en fonction du type de sac (ou d'agent de traitement) dans lequel on le met ? Si vous connaissez une astuce qui permettrait de faire ça de façon pas trop complexe (avec du code
) je suis preneur.... Merci !
-
coinroad
- Membre Naturel
- Messages: 17
- Enregistré le: 22 Déc 2020, 04:31
-
par coinroad » 06 Mai 2023, 20:57
Une solution simple pour faire varier le poids de chaque item en fonction du type de sac dans le problème de sac à dos multiple serait de représenter chaque item par plusieurs sous-items, un pour chaque type de sac possible. Chaque sous-item aurait le même bénéfice mais un poids différent, correspondant au poids de l'item dans le type de sac correspondant.
Par exemple, si on a un item A qui pèse 10 kg dans un sac de type 1 et 5 kg dans un sac de type 2, on peut le représenter par deux sous-items A1 et A2. A1 aurait un poids de 10 kg et A2 aurait un poids de 5 kg, mais les deux auraient le même bénéfice.
Ensuite, on pourrait utiliser l'algorithme du sac à dos multiple sur cette nouvelle représentation des items, en considérant chaque sous-item comme un item distinct. Cela permettrait de prendre en compte la variation de poids des items en fonction du type de sac, tout en utilisant une solution standard pour le problème de sac à dos multiple.
Mais comment gérer les sous-items dans un sac à dos multiple au niveau du code ?
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 41 invités