Algoritmo de corte de tablero bidimensional
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 = 1
2
horizontal1x2 is worth 2x2 - (cost of cutting) 1x1 = 3
2
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 = 2
1
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?