Borné Knapsack problème mis en place. Voulez-vous: une liste de tous les emballages possibles

Question

Au lieu que tout optimize, je veux la liste de tous les possibles - y compris « incomplète » - emballages du sac. Bien sûr, je pourrais boucle à travers tous les sous-ensembles de l'ensemble des objets et choisir ceux qui satisfont la contrainte de poids (peut être amélioré en plaçant une limite supérieure de la taille des sous-ensembles de regarder à travers), mais je voudrais vraiment quelque chose de plus efficace.

Merci.

Answer 1

Tout d'abord trier vos objets en poids. Puis emballer récursive le sac. Si le plus petit objet poids pas encore considéré ne correspond pas, ou nous avons aucun reste des objets, puis ajoutez le havresac en cours à notre liste et retour, ajoutez le reste du sac actuel à notre liste pour chaque objet dans la liste qui correspond à la mettre et essayer d'emballer le reste du sac avec des objets plus lourds que le dernier objet que nous voyagions.

Si nous pouvons emballer plus d'un élément de remplacer alors un type donné inférieur à moins de ou égal à.

Si nous avons plusieurs objets du même poids que nous devons trier d'abord du poids, puis par un 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)