c++ - whose - Cut rectangle in minimum number of squares




minimum number of squares whose sum equals to given number n (4)

Here is a greedy impl. As @David mentioned it is not optimal and is completely wrong some cases so dynamic approach is the best (with caching).

def greedy(m, n):
    if m == n:
        return 1
    if m < n:
        m, n = n, m
    cuts = 0

    while n:
        cuts += m/n
        m, n = n, m % n
    return cuts

print greedy(2, 7)

Here is DP attempt in python import sys

def cache(f):
    db = {}

    def wrap(*args):
        key = str(args)
        if key not in db:
            db[key] = f(*args)
        return db[key]
    return wrap


@cache
def squares(m, n):
    if m == n:
        return 1
    xcuts = sys.maxint
    ycuts = sys.maxint
    x, y = 1, 1
    while x * 2 <= n:
        xcuts = min(xcuts, squares(m, x) + squares(m, n - x))
        x += 1
    while y * 2 <= m:
        ycuts = min(ycuts, squares(y, n) + squares(m - y, n))
        y += 1
    return min(xcuts, ycuts)

I'm trying to solve the following problem:

A rectangular paper sheet of M*N is to be cut down into squares such that:

  1. The paper is cut along a line that is parallel to one of the sides of the paper.
  2. The paper is cut such that the resultant dimensions are always integers.

The process stops when the paper can't be cut any further.

What is the minimum number of paper pieces cut such that all are squares?

Limits: 1 <= N <= 100 and 1 <= M <= 100.

Example: Let N=1 and M=2, then answer is 2 as the minimum number of squares that can be cut is 2 (the paper is cut horizontally along the smaller side in the middle).

My code:

cin >> n >> m;

int N = min(n,m);
int M = max(n,m);
int ans = 0;

while (N != M) {
    ans++;
    int x = M - N;
    int y = N;
    M = max(x, y);
    N = min(x, y);
}

if (N == M && M != 0)
   ans++;

But I am not getting what's wrong with this approach as it's giving me a wrong answer.



The greedy algorithm is not optimal. On a 6x5 rectangle, it uses a 5x5 square and 5 1x1 squares. The optimal solution uses 2 3x3 squares and 3 2x2 squares.

To get an optimal solution, use dynamic programming. The brute-force recursive solution tries all possible horizontal and vertical first cuts, recursively cutting the two pieces optimally. By caching (memoizing) the value of the function for each input, we get a polynomial-time dynamic program (O(m n max(m, n))).


This is essentially classic integer or 0-1 knapsack problem that can be solved using greedy or dynamic programming approach. You may refer to: Solving the Integer Knapsack





algorithm