Je sais que les problèmes de sac à dos 2D et 3D sont des NPC, mais existe-t-il un moyen de les résoudre dans un délai raisonnable si les instances ne sont pas très compliquées? La programmation dynamique fonctionnerait-elle?
Par sac à dos 2D (3D), je veux dire que j'ai un carré (cube) et une liste d'objets, toutes les données sont en centimètres et mesurent au plus 20 mètres.
Réponses:
Knapsack peut être résolu par la programmation dynamique en pseudo-polynomial temps avec le nombre d'objets et la taille du sac à dos. Ainsi, tant que votre conteneur est petit (numériquement), vous pouvez résoudre le problème efficacement. Notez que vous pouvez régler en modifiant la résolution; pas besoin de mesurer un conteneur d'expédition au µm, mais les compteurs sont probablement grossiers (selon vos objets).O(nW) n W W
Le sac à dos peut également être approximativement arbitrairement bien calculé en temps polynomial (voir les schémas d'approximation en temps polynomial ).
Cependant, Knapsack ne considère que l'ajustement des nombres dans un autre nombre; il ne se soucie pas de la géométrie. Si vous avez besoin de "puzzle", vous avez besoin d'un autre problème; compte tenu de Tetris, c'est probablement beaucoup plus difficile que Knapsack .
la source
GREEDY trouvera toujours une solution raisonnable, mais pas nécessairement optimale. Placez simplement le plus gros objet qui tiendra à chaque fois dans le sac à dos. Arrêtez lorsque plus aucun objet ne rentre.
la source