Please allow ads on our site
Logindynamic programming and maximum length of a sequence of rectangles that fit into each other
Course Queries Syllabus Queries 3 years ago
User submissions are the sole responsibility of contributors, with TuteeHUB disclaiming liability for accuracy, copyrights, or consequences of use; content is for informational purposes only and not professional advice.
Answers (3)
manpreet 3 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:
manpreet 3 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:
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.
Similar Forum
Explore Other Libraries
Online Exams
Question Bank
Career News
Feeds
Full Forms
Dictionary
Interview Question
Gigs
Quotes
Lyrics
Videos
Courses
Blogs
Tutorials
Forum
Educators
Corporates
Tools
manpreet![Tuteehub forum best answer]()
Best Answer
3 years ago
Given a set of
nrectangles as{(L1, W1), (L2, W2), …….., (Ln, Wn)},LiandWiindicate the length and width of rectanglei, respectively. We say that rectangleifits in rectanglejifLi< LjandWi< 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:
Could you please help me improve my solution or find better one?