Tengo un problema con mi tarea.

Dada una tabla de dimensionesm x n se da, corta este tablero en piezas rectangulares con el mejor precio total. Una matriz proporciona el precio de cada tamaño de placa posible a través de la placa original sin cortar.

Considera un2 x 2 tablero con la matriz de precios:

3 4

3 6

Tenemos un costo constante para cada corte, por ejemplo1.
Pedazo de longitud1 x 1 vale la pena3.
Pieza horizontal de longitud1 x 2 vale la pena4.
Pieza vertical de longitud1 x 2 vale la pena3.
Todo el tablero vale6.

Para este ejemplo, elbeneficio óptimo es 9, porque cortamos el tablero en1 x 1 piezas. Cada pieza vale3 y hicimos un3 cortar, entonces4 x 3 - 3 x 1 = 9.

Segundo ejemplo

1 2

3 4

Ahora tengo que considerar todas las soluciones:

4 1x1 vale la pena4x1 - (cost of cutting) 3x1 = 12 horizontal1x2 is worth 2x2 - (cost of cutting) 1x1 = 32 vertical1x2 is worth 3x2 - (cost of cutting) 1x1 = 5 -> mejor beneficio óptimo1 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

He leído mucho sobre el algoritmo de corte de varillas, pero no tengo idea de cómo morder este problema. ¿Tienes alguna idea?