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 = 12 horizontal1x2 is worth 2x2 - (cost of cutting) 1x1 = 32 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 = 21 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?