Categories

See More
Popular Forum

MBA (4887) B.Tech (1769) Engineering (1486) Class 12 (1030) Study Abroad (1004) Computer Science and Engineering (988) Business Management Studies (865) BBA (846) Diploma (746) CAT (651) B.Com (648) B.Sc (643) JEE Mains (618) Mechanical Engineering (574) Exam (525) India (462) Career (452) All Time Q&A (439) Mass Communication (427) BCA (417) Science (384) Computers & IT (Non-Engg) (383) Medicine & Health Sciences (381) Hotel Management (373) Civil Engineering (353) MCA (349) Tuteehub Top Questions (348) Distance (340) Colleges in India (334)
See More

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

Course Queries Syllabus Queries

Max. 2000 characters
Replies

usr_profile.png

User

( 4 months 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< Lj and 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?

usr_profile.png

User

( 4 months 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:  
usr_profile.png

User

( 4 months 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:  

what's your interest