я проблема с домашней работой.

Учитывая табло размеровm x n Дайте, порежьте эту доску на прямоугольные части с лучшей общей ценой. Матрица дает цену для каждого возможного размера доски через оригинальную, необрезанную доску.

Рассмотрим2 x 2 плата с ценовой матрицей:

3 4

3 6

У нас есть постоянная стоимость для каждой резки, например1.
Кусок длины1 x 1 стоит3.
Горизонтальный отрезок длины1 x 2 стоит4.
Вертикальный отрезок длины1 x 2 стоит3.
Вся доска стоит6.

Для этого примераоптимальная прибыль 9потому что мы режем доску1 x 1 частей. Каждый кусок стоит3 и мы сделали3 вырезать, так4 x 3 - 3 x 1 = 9.

Второй пример:

1 2

3 4

Теперь я должен рассмотреть все решения:

4 1x1 штук стоит4x1 - (cost of cutting) 3x1 = 12 горизонтальный1x2 is worth 2x2 - (cost of cutting) 1x1 = 32 вертикальный1x2 is worth 3x2 - (cost of cutting) 1x1 = 5 -> лучшая оптимальная прибыль1 горизонтальный1x2 + 2 x (1x1) pieces is worth 2 + 2 - (cost of cutting) 2 = 21 вертикальный1x2 + 2 x (1x1) pieces is worth 3 + 2 - (cost of cutting) 2 = 3

Я много читал об алгоритме резки прута, но понятия не имею, как решить эту проблему. У тебя есть идеи?