Find the optimal shelf placement

Assignment Help Basic Computer Science

Reference no: EM131366263

Consider the problem of storing n books on shelves in a library. The order of the books is fixed by the cataloging system and so cannot be rearranged. Therefore, we can speak of a book bi, where 1 ≤ i ≤ n, that has a thickness ti and height hi. The length of each bookshelf at this library is L. Suppose all the books have the same height h (i.e. , h = hi = hj for all i, j) and the shelves are all separated by a distance of greater than h, so any book fits on any shelf. The greedy algorithm would fill the first shelf with as many books as we can until we get the smallest i such that bi does not fit, and then repeat with subsequent shelves. Show that the greedy algorithm always finds the optimal shelf placement, and analyze its time complexity.

Reference no: EM131366263

Questions Cloud

Component of plasma membrane : Consider a plant cell that makes a particular protein that is a necessary component of its plasma membrane. Trace the pathway this protein will take, beginning with its synthesis at the ribosome bound to the endoplasmic reticulum (which is where a..

Explain the relevant historical background : Do you summarize and explain the relevant historical background - Do you clearly explain the relationship between the historical background and the literary work?

Did you know that the moon may be made of cheese : The purpose of this assignment is to help you distinguish between different types of information sources and evaluate sources of information for credibility. Scientists and scholars use information from a variety of sources, some of them scholarly..

Plasma osmolarity during dehydration or water loading : Explain why we do not see significant changes in plasma osmolarity during dehydration or water loading.

Find the optimal shelf placement : Show that the greedy algorithm always finds the optimal shelf placement, and analyze its time complexity.

Describe the procedures for compliance plans : In a 4-page paper, describe the procedures for each of the two compliance plans. Break each procedure section into 2 pages each

Environmental issue facing community : Imagine that you have been asked to educate the members of your community on this environmental issue.

Identify one or two behavioral risk factors : Phase 3 of the PRECEDE-PROCEED model is the education and ecological assessment. After the key risk factors have been identified, they are classified into three categories: Predisposing, reinforcing, and enabling factors. Approaches to these facto..

Comparing the characters hamlet and robert wringhim : Write at least 400 words comparing the characters Hamlet and Robert Wringhim and the events of their lives. What elements of comparison and contrast can you see between these two?

User Account

All Pages