Algoritmo de corte da placa bidimensional
Estou com problemas com minha lição de casa.
Dada uma tabela de dimensõesm
x n
é dado, corte esta placa em pedaços retangulares com o melhor preço total. Uma matriz fornece o preço de cada tamanho de placa possível através da placa original, sem cortes.
Considere um2 x 2
placa com a matriz de preços:
3 4
3 6
Temos um custo constante para cada corte, por exemplo1
.
Pedaço de comprimento1 x 1
Vale3
.
Peça horizontal de comprimento1 x 2
Vale4
.
Peça vertical de comprimento1 x 2
Vale3
.
Toda a pensão vale a pena6
.
Para este exemplo, olucro ideal é 9, porque cortamos a placa1 x 1
peças. Cada peça vale a pena3
e fizemos um3
corte, então4 x 3
- 3 x 1
= 9
.
Segundo exemplo:
1 2
3 4
Agora eu tenho que considerar todas as soluções:
4
1x1
peças vale a pena4x1 - (cost of cutting) 3x1 = 1
2
horizontal1x2 is worth 2x2 - (cost of cutting) 1x1 = 3
2
vertical1x2 is worth 3x2 - (cost of cutting) 1x1 = 5
-> melhor lucro ideal1
horizontal1x2 + 2 x (1x1) pieces is worth 2 + 2 - (cost of cutting) 2 = 2
1
vertical1x2 + 2 x (1x1) pieces is worth 3 + 2 - (cost of cutting) 2 = 3
Eu li muito sobre o algoritmo de corte de haste, mas não tenho idéia de como morder esse problema. Você tem alguma ideia?