Sac à dos borné Problème de configuration. Vouloir: une liste de tous les empaquetages possibles

Question

Plutôt que d'optimiser quoi que ce soit, je veux énumérer tous les possibles - y compris les "incomplètes" - garnitures du sac à dos. Bien sûr, je pourrais parcourir tous les sous-ensembles de l'ensemble et choisir ceux qui satisfont la contrainte de poids (peut être améliorée en plaçant une limite supérieure sur la taille des sous-ensembles à regarder), mais j'aimerais vraiment quelque chose de plus efficace.

Merci.

Answer 1

Commencez par trier vos objets en fonction du poids. Puis récursivement emballer le sac à dos. Si le plus petit objet de poids non encore considéré ne rentre pas, ou si nous n'avons aucun objet restant, ajoutez le sac actuel à notre liste et revenez, sinon ajoutez le sac actuel à notre liste pour chaque objet de la liste qui le place et Essayez d'emballer le reste du sac avec des objets plus lourds que le dernier objet emballé.

Si nous pouvons emballer plus d'un article d'un type donné, remplacez-le par moins de inférieur ou égal à.

Si nous avons plusieurs objets de même poids, nous devons trier d'abord en poids, puis par ordre arbitraire, et l'utiliser.

PackKnapsack(knapsack, objects) 
    add knapsack to list 
    if objects is empty return 
    if smallest object does not fit return 
    for each object in order from smallest to largest 
     if currentobject does not fit 
     break 
     PackKnapsack(knapsack + currentObject, objects heavier than current object)