Home > programming > finding max number of 3D box that forms the longest sequence

finding max number of 3D box that forms the longest sequence


give a set of 3d boxes with dimensions like:

A, 3,4,5

B 5,3,1

C2,7,9,

D 8,8,10

E 9,10,12

A cannot fit into B, but A can fit into  D, E.

So the result will be A, D, E, which is the longest sequence.

 

R formulates it into a LCS problem, but it’s the same complexity as my formulation.

I formulate it into a graph diameter problem, whose dominant complexity is all pair shortest path, O(N^3).

really nice problem.

Advertisements
Categories: programming
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: