/tin-cut

Counting minimum cost of cutting tinware into squares

Primary LanguageJava

Minimum Cost to of cutting tin into squares

Altrnative solution to problem from www.geeksforgeeks.org/minimum-cost-cut-board-squares/

A board (tin) of length m and width n is given, we need to break it into m*n squares such that cost of breaking is minimum. Cutting cost for each edge will be given for the board. In short we need to choose such a sequence of cutting that toatal cost is minimized.

step 0 Cuts are made starting from the most expensive, with the vertical and horizontal cuts being mixed up.

step 1

step 2

step 3

step 4

step 5

step 6

step 7

step 8

total cost=42

Cutting

Fragment before cutting:
Fragment(startX, startY, dimX, dimY));

Two fragments after vertical cutting at cutPosition:
Fragment(startX, startY, cutPosition, dimY));
Fragment(cutPosition + 1, startY, endX - cutPosition, dimY));

before cutting

after cutting - fragment 1 startX = startX = 1;
startY = startY = 1;
dimX = cutPosition = 5;
dimY = dimY = 4;

after cutting - fragment 2 startX = cutPosition + 1 = 5+1 = 6;
startY = startY = 1;
dimX = endX - cutPosition = 6-5 = 1;
dimY = dimY = 4;