dynamic programming and maximum length of a sequence of rectangles that fit into each other

Course Queries Syllabus Queries 2 years ago

0 2 0 0 0 tuteeHUB earn credit +10 pts

5 Star Rating 1 Rating

Posted on 16 Aug 2022, this text provides information on Syllabus Queries related to Course Queries. Please note that while accuracy is prioritized, the data presented might not be entirely correct or up-to-date. This information is offered for general knowledge and informational purposes only, and should not be considered as a substitute for professional advice.

Take Quiz To Earn Credits!

Turn Your Knowledge into Earnings.

tuteehub_quiz

Answers (2)

Post Answer
profilepic.png
manpreet Tuteehub forum best answer Best Answer 2 years ago

Given a set of n rectangles as {(L1, W1), (L2, W2), …….., (Ln, Wn)}Li and Wi indicate the length and width of rectangle i, respectively. We say that rectangle i fits in rectangle j if Li< Ljand Wi< Wj.

I need help designing a O( nˆ2 ) dynamic programming algorithm that will find the maximum length of a sequence of rectangles that fit into each other.

I made an attempt, but it is not working in some cases, which are as follows:

LR(i, j)= { 2+ LR(i-1, j-1)  if (Li< Lj and Wi< Wj) or (Lj< Li and Wj< Wi)

             Max ( LR(i+1, j), LR (I, j-1)  otherwise   }

Could you please help me improve my solution or find better one?

profilepic.png
manpreet 2 years ago


With DP you can do it as follows:

  • Sort the rectangles by decreasing width, and sort ties by decreasing height
  • For each index in the array of rectangles, determine the best solution if that rectangle is the first one taken (the outermost containing rectangle), and store it for later lookoup
  • Use recursion to determine the greatest number of rectangles that can fit when the currentrectangle is taken (1) or not taken (2). Take the greatest result of both.

Here is an implementation in JavaScript which you can run here:

 

function maxNumberOfFittingRectangles(rectangles) {
     // Storage of optimal, intermediate results (DP principle), 
     //    keyed by the index of the first rectangle taken
    let memo = new Map;

    // Take a copy of rectangles, and sort it in order of decreasing width, 
    //    and if there are ties: by decreasing height
    rectangles = [...rectangles].sort( (a, b) => (b.width - a.width) 
                                              || (b.height - a.height) );
    
    function recurse(maxHeight, startIndex) {
        for (let i = startIndex; i < rectangles.length; i++) {
            if (rectangles[i].height <= maxHeight ) { // Can fit
                // Try a solution that includes rectangles[i]
                // - Only recurse when we did not do this before
                if (!(memo.has(i))) memo.set(i, recurse(rectangles[i].height, i+1)+1);
                // Also try a solution that excludes rectangles[i], and 
                // return best of both possibilities:
                return Math.max(memo.get(i), recurse(maxHeight, i+1));
            }
        }
        return 0; // recursion's base case
    }
    
    let result = recurse(Infinity, 0);
    // Display some information for understanding the solution:
    for (let i = 0; i < rectangles.length; i++) {
        console.log(JSON.stringify(rectangles[i]), 
                    'if taken as first: solution = ', memo.get(i));
    }
    
    return result;
}

// Sample data
let rectangles = [
    { width: 10, height:  8 },
    { width:  6, height: 12 },
    { width:  
                                                    
                                                    
0 views   0 shares

No matter what stage you're at in your education or career, TuteeHub will help you reach the next level that you're aiming for. Simply,Choose a subject/topic and get started in self-paced practice sessions to improve your knowledge and scores.