Como calcular o mínimo de desperdício ao adaptar tubos

Question

Eu tenho um problema bastante matemática eu preciso para resolver:

A tarefa consiste em cortar um número pré-definido de tubos de tubos de comprimento fixo com uma quantidade mínima de material de resíduos.

Então, digamos que eu quero cortar 10 tubos de 1m e 20 2,5m tubos de tubos com um comprimento padronizado de 6m.

Eu não tenho certeza o que um algoritmo para este tipo de problema seria semelhante?

Eu estava pensando para criar uma lista de variações dos diferentes tubos de tamanho, encaixá-los em tubos de tamanho padrão e em seguida, escolher a variação com o mínimo de desperdício.

Em primeiro lugar eu não tenho certeza se não há outras e melhores maneiras de atacar o problema.

Em segundo lugar eu não encontrar uma solução como eu iria criar tal lista variações a.

Qualquer ajuda é muito apreciada, obrigado!

Answer 1

Eu acredito que você está descrevendo o problema de corte de estoque . Algumas informações adicionais podem ser encontradas aqui .

Answer 2

Esta é conhecida como a corte da problema. Wikipedia tem uma série de referências que podem ajudá-lo a encontrar pistas para um algoritmo que funciona.