Asking help from smart math people (Yet Again)

[wasab]

 

What does bk+1 mean? My gut is telling me this is a subset sum problem but I am not sure what I am supposed to sum up. 

@Dash Lambda

Help me once again, pretty please. 

[dcgreen2k]

I'm pretty sure what it's saying is that the top shelf has books 1 through k, and then the first book of the second shelf would be number k+1. This means that if the top shelf has 40 books, the first book of the second shelf would be number 41. (k = 40, k+1 = 41)

[wasab]

17 minutes ago, thegreengamers said:

I'm pretty sure what it's saying is that the top shelf has books 1 through k, and then the first book of the second shelf would be number k+1. This means that if the top shelf has 40 books, the first book of the second shelf would be number 41. (k = 40, k+1 = 41)

so k is just denoting the k^th book out all the books? My brain is now coming up with this picture. The optimal solution takes in 3 parameters like this

OPT(K^th  book, Maximum Width W, a height which is initially 0 ). The question wants me to minimize height. 

I am not sure What I am supposed to do next from here.... 

 

Edit:

Actually, do I even need to use dynamic programming here? Can I just make a naive greedy algorithm like all the tallest book go into one shelf, if it is full, fill the next shelf with the next tallest books and so on. Would that already minimize the height? Do the width and K+1 play a factor in this?

 

I am quite confused.....

[dcgreen2k]

5 minutes ago, wasab said:

so k is just denoting the k^th book out all the books? My brain is now coming up with this picture. The optimal solution takes in 3 parameters like this

OPT(K^th  book, Maximum Width W, a height which is initially 0 ). The question wants me to minimize height. 

I am not sure What I am suppose to do next from here.... 

Yes, the subscript of a variable is used to give extra information about it, usually the number of that variable when it's in a series. As for how to make an algorithm, I have no clue.

[Dash Lambda]

An important thing to note: The books must remain in their original order, so you cannot change their order by putting the biggest books on one shelf, next biggest books on the next, etc. The only thing you can change is at what point you move to the next shelf. So your function at each shelf just needs to know which book the previous shelf stopped at.

[wasab]

14 hours ago, Dash Lambda said:

An important thing to note: The books must remain in their original order, so you cannot change their order by putting the biggest books on one shelf, next biggest books on the next, etc. The only thing you can change is at what point you move to the next shelf. So your function at each shelf just needs to know which book the previous shelf stopped at.

So I don't have to fill up the entire width of a shelf? 

[Dash Lambda]

35 minutes ago, wasab said:

So I don't have to fill up the entire width of a shelf? 

No, if you did then there would only be one possible way to arrange the books.

[wasab]

1 hour ago, Dash Lambda said:

No, if you did then there would only be one possible way to arrange the books.

After googling around, I actually found a pseudo-code for an algorithm that optimally solves this problem. I don't understand it though   

 

[Dash Lambda]

9 hours ago, wasab said:

-snip-

I'm actually a little confused by that pseudocode too. I'm not sure why they bother with "cost," they flip-flop over whether or not they use assignments, and they don't define everything they use...

 

Anyway, your function needs to know which books it can use at each shelf and it needs to return the minimum height possible starting from that shelf going down. This is a dynamic programming problem because each shelf can ignore the shelves above it. Each time you move to the next shelf you look at a smaller subproblem.

 

The fact that you're not allowed to rearrange the books means that your function need only worry about how many books it puts on each shelf. So for each shelf, your function could try using the first book, the first two books, the first three books, and so-on until it can't fit any more on the shelf, each time calling itself for the next shelf down.

[wasab]

13 hours ago, Dash Lambda said:

I'm actually a little confused by that pseudocode too. I'm not sure why they bother with "cost," they flip-flop over whether or not they use assignments, and they don't define everything they use...

 

Anyway, your function needs to know which books it can use at each shelf and it needs to return the minimum height possible starting from that shelf going down. This is a dynamic programming problem because each shelf can ignore the shelves above it. Each time you move to the next shelf you look at a smaller subproblem.

 

The fact that you're not allowed to rearrange the books means that your function need only worry about how many books it puts on each shelf. So for each shelf, your function could try using the first book, the first two books, the first three books, and so-on until it can't fit any more on the shelf, each time calling itself for the next shelf down.

So algorithm, in words would look like this:

for every book, cost(i) = cost of placing this book and all the ones before on the shelf + the costs of all the bottom shelves(by recursively calling itself), assuming they are not greater than the width of the bookshelf of course. if cost is less than the current cost(i), replace that as the optimal solution..... right? 

 

[Dash Lambda]

20 minutes ago, wasab said:

So algorithm, in words would look like this:

For every book, cost(i) = cost of placing this book and all the ones before on the shelf + the costs of all the bottom shelves(by recursively calling itself), assuming they are not greater than the width of the bookshelf of course. if cost is less than the current cost(i), replace that as the optimal solution..... right? 

Yep, that's about right.

 

(Sorry I took so long to reply.)