675 Design and Analysis of Algorithms
675Â Design and Analysis of Algorithms
Â
2. You are given a series of boxes. Each box i has a rectangular base with
width Wi and length Li, as well as a height Hi. You are stacking the boxes,
subject to the following: In order to stack a box i on top of a second box
j, the width of box i must be strictly less than the width of box j and the
length of box i must be strictly less than the length of box j (assume that
you cannot rotate the boxes to turn the width into the length). Your job is
to make a stack of boxes with total height as large as possible. You can only
use one copy of each box. Design a dynamic programming algorithm to solve
this problem.
Part a: Draw and explain the DAG corresponding to this problem. Hint:
What is a reasonable way to sort the boxes so that all edges go from earlier
nodes to later nodes?
Â
Part b: Describe an efficient algorithm to determine the height of the tallest
possible stack. You do not need to write pseudocode (though you can if you
want to), but in order to get full credit, you must include all the details that
someone would need to implement the algorithm. Hint: think about what
the subproblems should be.
Answers
Status NEW
Posted 29 Apr 2017 04:04 AM
My Price 8.00
-----------
Attachments
file 1493441973-Solutions file 2.docx preview (51 words )
H-----------ell-----------o S-----------ir/-----------Mad-----------am
-----------
Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------.
-----------
Th-----------ank----------- yo-----------u
-----------
Not Rated(0)