Zagadka na rozluźnienie :)

Trafiłem na takie zadanie:
Załóżmy, że mamy kawałek tkaniny T o rozmiarze A×B, gdzie A i B są dodatnimi liczbami całkowitymi, oraz zbiór S = {p1, p2, . . . , pn} produktów, które mogą być wykonane z tej tkaniny. Na każdy z produktów pi (gdzie i = 1, . . . , n) o końcowej cenie ci, potrzebujemy tkaniny wielkości prostokąta wymiaru ai ×bi, gdzie ai i bi są dodatnimi liczbami całkowitymi. Zakładając, że maszyna tnąca może wykonywać zawsze tylko cięcia pionowe lub poziome, rozcinając dany kawałek na dwa mniejsze prostokąty, zaproponuj algorytm oparty na programowaniu dynamicznym, który dla danego kawałka tkaniny T oraz zbioru produktów S wyznaczy optymalne —w sensie maksymalizacji sumy cen końcowych — podzielenie materiału T. (Nie jest wymagane, aby każdy z produktów znalazł się w ofercie, a dany produkt może wystąpić wiele razy.)

Mam pomysł na to ale chciałem też poznać Wasze :>

Taka ładna pogoda dzisiaj, wyszedłbyś na pole

U mnie pada deszcze ;) A poza tym ja lubię czasem rozwiązać coś dla 'sportu'. Ty nie musisz [browar]

Mamy tablicę T o rozmiarze m, n. Trzymamy w niej maksymalne uzyski dla płótna m x n i odpowiadające im mapy (rodzaj szmaty => ilość).

T[1, 1], T[0, ] oraz T[, 0] wiadomo jak policzyć.

T[a, b] = albo najdroższa szmata rozmiaru a x b, albo maksimum po rozcięciach pionowych, albo maksimum po rozcięciach poziomych. Dla każdego rozcięcia jego uzysk otrzymujemy sumując odpowiednie dwie komórki z tablicy.

Ten problem się nazywa: "problem optymalnego rozkroju". Poszukaj w google. nawet na tym forum było coś podobnego wiele razy.
Problem nie jest prosty, a ty masz dodatkowy wiąz cięcia do końca, ale jestem pewien, że ktoś i coś takiego analizował.

No właśnie dzięki temu, że tniemy do końca problem jest prosty.

Jak rozetniemy jakiś prostokąt na dwa prostokąty to dostajemy dwa mniejsze już obliczone podproblemy.