My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
January 23rd, 2011, 11:00 AM   #1
Joined: Jan 2011
From: Russian Federation

Posts: 2
Thanks: 0

Optimization problem Recursion/Dynamic programming

Dear friends,
There is an optimization program I am writing. I have to write it in 3 different ways. Dynamic approach, recursive approach and memoization+recursive approach. I wrote the codes for each, they all compiled. According to my prof, the algorithms I chose were poor, and do not guarantee the true optimal result. I would like to have your attention on the recursive approach for solving my problem for now.

The problem itself is as follows:

There is a random number of 2D blocks with different dimensions each, (hight x width)
These blocks are arranged in a certain order that can't be modified.

Suppose there is a bookshelf-like container with shelves. All shelves have the same length, but each shelf could have a different height. We don't yet know how many shelves there are in a bookshelf.

My job is to take that string of 2D blocks and distribute them inside that bookshelf in such a way, that we get the minimal height of a bookshelf. The height of a bookshelf is determined by a sum of heights of all the shelves. The height of each shelf is determined by the highest block in that shelf (MAX(Block.height))

-The range of a shelf (length) is given
-The number of blocks and their dimensions are given

To make it easier to understand, I have attached a .pdf file that graphically illustrates the problem. I recommend to have a look at it at this point.

There are many ways for us to arrange them, but we need the most optimal (minimal) height of the bookshelf.
At first it may seem like its a greedy algorithm, but it's not! There are cases where its better not to fit
the shelf completely, but instead skip to the next shelf, leaving the previous one unfilled.

My approach to solution:

We can see that this system accepts a recursive strategy.
At first, I need to figure out how many blocks can actually fit the shelf completely. Let us call this value: "int fitted". I'll skip this step in here. Suppose we found
int fitted.
The main formula here, is as follows:

int N; //N is given, number of blocks
int begin = 0; //begin is the first block in the shelf
//0 from main() (initial step). begin later accepts a different value at the next recursion.

for (int i=begin; i<fitted; i++)
MAX[i] = max(Block_height, begin, i) + max(Block_height, begin+1+i, N);; //Block.height is the array of heights of each block.
this cycle defines the height of a particular shelf under different configurations (first with 1 block, then 2 blocks, 3 up to how many fit) + The max(block_height) of the rest of the string of Blocks (not yet broken up into shelves). After that is done, I find the argmin(MAX[]) to find out the most optimal configuration for that particular shelf. (i.e. number of blocks accepted in a particular shelf under the best configuration)

I repeat the process by calling this function again from that same function (recursion) but now with a different int begin value

int begin = accepted+1; //the next block after the last accepted block in a previous shelf.
By adding up the heights of resulting shelves, I find the optimal value of the hight of the whole bookshelf.

So my professor has a problem with that formula. He says that this formula doesn't guarantee the optimal value.
To be specific, he pointed out the second part of the formula.
MAX[i] = max(Block_height, begin, i) + max(Block_height, begin+1+i, N)
To be honest, I think he has a point :P


How should I solve this problem? I would first prefer some help on the recursive approach that I've described. I believe that once I get the recursion down, I may be able to figure out the dynamic approach. If you guys need my source code, I will provide it to you. But this particular part (the main formula) is what I need help with.
Thanks for your time
Attached Files
File Type: pdf Blocks.pdf (39.1 KB, 52 views)
cryptoxic is offline  
January 29th, 2011, 02:25 AM   #2
Joined: Jan 2011
From: Russian Federation

Posts: 2
Thanks: 0

Re: Optimization problem Recursion/Dynamic programming

Very helpful forum :/
cryptoxic is offline  
June 19th, 2011, 02:08 AM   #3
Joined: Jun 2011

Posts: 4
Thanks: 0

Re: Optimization problem Recursion/Dynamic programming

Can you please upload your source code?
And also which Compiler are you using?
mirzausman is offline  

  My Math Forum > Science Forums > Computer Science

optimization, problem, programming, recursion or dynamic

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
linear programming problem joody Calculus 2 March 30th, 2014 01:27 AM
Dynamic Programming-Grouping of objects with minimum cost evinda Applied Math 0 December 21st, 2013 01:11 PM
The linear programming problem eewia17 Real Analysis 0 January 28th, 2013 07:14 AM
Linear programming problem niaboc Algebra 2 October 1st, 2012 09:00 PM
Recursion Problem stbrian Computer Science 4 October 16th, 2007 12:40 PM

Copyright © 2019 My Math Forum. All rights reserved.