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

Max. 2000 characters Replies 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? 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: 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:

Ra
04-Sep-2019

2 Replies

Ra
05-Sep-2019
UGC NET Eligibility

2 Replies 11-Sep-2019
Which Is Best Institute/Platform For Data Science Course??

0 Replies 12-Sep-2019

0 Replies

Lu
10-Jul-2019

2 Replies