CODEWITHSUNDEEP
javaalgorithm
user1352234
user1352234

Reputation: 35

Bin packing with a twist?

I've been trying to look for some sort of an algorithm that will take care of the problem i have. The closest thing that i've come across is that of a bin packing algorithm but i don't think its quiet what i'm looking for.

This document is a graphical representation of my problem and the expected output: http://www.scribd.com/doc/90871434/Rectangles

My thoughts where to find the lowest(height) rectangle and create a rectangle that fits the width of the remaining rectangles, and with some recursion figure out the rest.

What i'm basically trying to do is find the smallest amount of vertically stacked rectangles, given N amount of horizontally placed rectangles.

Doing this in Java i have a HashMap with the input rectangles.

Any ideas, code, links ? thanks

Upvotes: 1

Views: 731

Answers (2)

bdecaf
bdecaf

Reputation: 4732

I think you should use divide and conquer.

When you find the lowest rectangle you also split your data set. The next rectangles are either exclusively in the left or right set. And that works recursively.

Upvotes: 1

Jens Schauder
Jens Schauder

Reputation: 81862

Find the smallest rectangle.

Create your first resulting rectangle out of that.

Determine the remaining rectangles.

Apply the algorithm on all continuous groups of remaining rectangles.

Upvotes: 2

Related Questions