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

##### 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:
``````
``` ```
``` 52 Shiv Thapa User 11-Jun-2019 ( 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: Similar Discussions Ra 04-Sep-2019 Lecturer Course Queries Competitions/Entrance Exams User : ravi mahawar 2 Replies Ra 05-Sep-2019 UGC NET Eligibility Course Queries Competitions/Entrance Exams User : ravi mahawar 2 Replies 11-Sep-2019 Which Is Best Institute/Platform For Data Science Course?? Course Queries Syllabus Queries User : Pranjal Goel 0 Replies 12-Sep-2019 Test Exam Strategy Title Course Queries Syllabus Queries User : Naushad Malik 0 Replies Lu 10-Jul-2019 Google cloud Serverless Technology Course Queries Syllabus Queries User : Lucky Negi 2 Replies ```
``` what's your interest Question Bank Exams Courses Trainings Webinars Career News Articles Jobs Internships Post Projects Buy Services Find Projects Sell Services Post Content Question Bank Online Exams Courses Trainings Webinars Career News Articles Jobs Internships Post Projects Buy Services Find Projects Sell Services Post Content Object Oriented Programming Interview Aspire Motorola Php Coding Javascript Interview Lion Bridge Chemical Engineering Gas Turbine Clinical Science Advanced C Skill Test Mock Exam Matlab Karnataka PSC (KPSC) CMAT Community Medicine Nursing NEET-UG UKSEE CEPT Entrance Exam Landscape Oncology Urban CG Pre BEd RPSF SBI CEED Security And Investment Law Math Education Commerce Hotel Management Agriculture Humanities IT Psychology Humanities IT Pharmacy Animal Biochemistry Paramedical Aviation Oral Surgery Accounts & Finance Graphics & Design Typegraduation Medical Architecture Humanities Railways Banking, Finance & Insurance Mass Communication Engineering Information Technology Information Technology Science Teaching Mass Communication Engineering Mass Communication Marine Deck Department Airport Company Secretary Tower Technician Agriculture, Dairy Pulp and Paper 32 Site Engineering Mining , Quarrying Automobile , Auto Anciliary , Auto Components Export, Import Printing , Packaging BPO , Call Centre, ITES Accounting , Finance Advertising , PR, MR, Event Management Recruitment,Staffing Web Development Data Entry 3D Animation Brand Marketing Translation Brand Management Marketing Internet Marketing Logo Design Online Writing Apple iBooks Author Advertising Recruitment Services Reviews Category Comming soon.. WordPress Web Development Content Writing PHP iOS Development HTML5 Engineering Search Engine Marketing Academic Writing Career Guidance Internet Marketing App Developer Programming Email Marketing Productivity Visual Design Training Tips Aviation Civil Services Mass Communication Nursing Information Technology Medical Leaving Your Job Engineering Humanities Marketing Category Comming soon.. Offers Category Comming soon.. ```
``` 11-Jun-2019 3 answers 26 votes Jadav Payeng User Latest Discussions Is It Possible To Live-stream Video From Windows Azure User : Sunanda Sharma Internet of Things Trust Store Vs Key Store - Creating With Keytool User : Priyanka Chadda Internet of Things How To Check If Array Is Not Empty? [duplicate] User : Raman Tripathi Internet of Things Can An Mqtt Broker Be Configured Not To Echo Messages On A Topic? User : Shreya Bansal Internet of Things Trending Categories Career Talk (85136) General Tech (5212) Course Queries (2878) Interviews (1022) Mobile Technologies (311) Web Technologies (232) Digital Marketing (216) Internet of Things (216) Creative Design (98) Commerce & Accounting (24) Announcement / News (13) Job Openings/Vacancy Notifications (11) Policies & Procedures (9) Tips & Tricks (8) Results (6) Also See Online Exams Question Bank Guess Papers Question Papers Courses Admission Trainings/Workshops Internships Placement Jobs Services Projects Forums Feeds Career News Articles Our Community Scholar (51k+) Corporate (341k+) Campus (11k+) Consultant (28) Institute (18) Affiliate (6) ```
``` ```
``` ```
``` \$(document).ready(function () { let editor; var csrf_token = 'fIzqlM3xQJB4nhAJAFakvYNHQcWtkCkPw6skc7ae'; \$('#submit_response').click(function(){ \$('#chatter_form_editor').submit(); }); \$(document).on('click', '.update_chatter', function(){ console.log('update'); post_id = \$(this).data('id'); console.log(editor.getData()); body=editor.getData(); var url = "https://www.tuteehub.com/forum/posts/update"; var data = {_token: csrf_token, id: post_id,body:body}; \$.ajax({ url: url, data: data, method: 'post', success: function (data, status, xhr) { console.log(data); if (data.status == 1) { \$("#main-suscess-message").text(data.message); \$("#main-suscess-message").show(); setTimeout(function () { \$("#main-suscess-message").hide(); }, 3000); window.location.reload(); } else { \$("#main-failure-alert").text(data.message); \$("#main-failure-alert").show(); setTimeout(function () { \$("#main-failure-alert").hide(); }, 3000); } }, failure: function (status) { console.log(status); } }); }); \$(document).on('click','.chatter_edit',function(){ console.log('edit'); \$('#update-section,#edit-section,#response-body').toggleClass('d-none'); }) \$(document).on('click','.cancel_chatter',function(){ console.log('cancel'); \$('#update-section,#edit-section,#response-body').toggleClass('d-none'); }) \$('.delete_response').click(function(){ post_id = \$(this).data('id'); var url = "https://www.tuteehub.com/forum/posts/delete"; var data = {_token: csrf_token, id: post_id}; \$.ajax({ url: url, data: data, method: 'delete', success: function (data, status, xhr) { console.log(data); if (data.status == 1) { \$("#main-suscess-message").text(data.message); \$("#main-suscess-message").show(); setTimeout(function () { \$("#main-suscess-message").hide(); }, 3000); window.location.reload(); } else { \$("#main-failure-alert").text(data.message); \$("#main-failure-alert").show(); setTimeout(function () { \$("#main-failure-alert").hide(); }, 3000); } }, failure: function (status) { console.log(status); } }); }); // ClassicEditor.create( document.querySelector( '#ckeditorupdate' ) ).then( newEditor => { // editor = newEditor; // } ).catch( error => { } ); // ClassicEditor.create( document.querySelector( '#ckeditor' ) ).catch( error => { } ); }); Popular Category Career Talk General Tech Course Queries Interviews Mobile Technologies Web Technologies Digital Marketing Internet of Things Creative Design Commerce & Accounting Announcement / News Job Openings/Vacancy Notifications Policies & Procedures Tips & Tricks Results Recent Category Internet of Things Campus Diaries Digital Marketing IoT Frameworks Facebook Marketing API Web Development Mobile Computing General Tech Course Queries HR Files Work & Career Exam Hub Popular Tech Job Search Queries General Trending Tags MBA B.Tech Engineering Class 12 Study Abroad Computer Science And Engineering Business Management Studies BBA Diploma CAT B.Com B.Sc JEE Mains Mechanical Engineering Exams Courses Internships Jobs Projects Services TuteeHUB is a technology driven cloud platform to "Learn, Work & Earn" through learning products, self-development services, employment and remote work options with integrated marketing & promotions opportunities. 011-42427761 info@tuteehub.com Our Services Question Bank Question Papers Guess Papers Online Exams Jobs Internships Exclusive Services Courses & Admissions Training & Workshops Projects Services Affiliate Marketing Webinars Insights Career News Articles Feeds Help & Supports Forum Help Desk FAQ Our Community       About Company About Us How It Works Privacy Policy Terms & Conditions Contact Us Social Connect App Download © 2019 TuteeHUB, All Rights Reserved. if (window.location.href.indexOf("user/login") <= -1){ window.fbAsyncInit = function(){ FB.init({ appId:'1123210154481974', status:true, cookie:true, xfbml:true}); FB.getLoginStatus(function(response){ if (status) { \$('.zEWidget-launcher').hide(); var js; js = document.createElement('script'); js.async = true; js.src = "//widget.manychat.com/504149259791561.js"; document.getElementsByTagName('head')[0].appendChild(js); }else{ \$('.zEWidget-launcher').show(); } }); }; // Load the SDK Asynchronously (function(d){ var js, id = 'facebook-jssdk'; if (d.getElementById(id)) {return;} js = d.createElement('script'); js.id = id; js.async = true; js.src = "//connect.facebook.net/en_US/all.js"; d.getElementsByTagName('head')[0].appendChild(js); }(document)); } ```