Algoritmos para Mochila Bidimensional e Tridimensional

Eu sei que os problemas de mochila 2D e 3D são NPC, mas existe alguma maneira de resolvê-los em tempo razoável se as instâncias não forem muito complicadas? A programação dinâmica funcionaria?

Com mochila 2D (3D), quero dizer que tenho um quadrado (cubo) e uma lista de objetos, todos os dados estão em centímetros e no máximo 20m.

A mochila pode ser resolvida pela programação dinâmica em tempo pseudo-polinomial$O(nW)$ com $n$ o número de objetos e $W$o tamanho da mochila. Portanto, contanto que seu contêiner seja pequeno (numericamente), você poderá resolver o problema com eficiência. Observe que você pode ajustar$W$alterando a resolução; não é necessário medir um contêiner de remessa para o µm, mas é provável que os medidores sejam grosseiros (dependendo dos objetos).

A mochila também pode ser aproximada arbitrariamente bem em tempo polinomial (consulte esquemas de aproximação em tempo polinomial ).

No entanto, a mochila apenas considera números de montagem em outro número; não se preocupa com a geometria. Se você precisa "confundir", precisa de outro problema; considerando Tetris, isso provavelmente é muito mais difícil do que a mochila .

A GREEDY sempre encontrará uma solução razoável, mas não necessariamente a ideal. Basta colocar o maior objeto que caberá sempre na mochila. Pare quando não houver mais objetos.