Tower of boxes

[poko]

hi there,

i got this task last week but can't find a good algorithm to solve the problem. So here is the description:

You can build a stable tower with building bricks by not putting bigger bricks to smaller ones and if you don't put harder bricks into lighter ones. Make a programme which gives you the highest possible tower with n number of bricks.
Input:
In the first row of in.txt there is the number of cubes n (1 =<n =<1000). the following n line consisting two positive integer, a cube's sidelength and weight (both of them are not higher than 2000) there are no similar cubes which sidelength and wieght is the same
Output:
you have to write the highest possible stable tower's m number into out.txt. into the second row you have to write in the ordinal number m of the tower from bottom to top. by the height of the tower we mean the amount of all of the cubes's sidelength (not the number of cubes). if there are more than one solution, you can give whatever you want

example for input and output:
Input: Output:
5 3
10 3 2 1 5
20 5
15 6
15 1
10 2

there are limits on the program. Time limit: 0.2 sec. Memory limit: 16 Mb

I hope you can help me to solve this, i need to finish this till sunday. thx for all help

[poko]

Oh soz, the input and output is a little bit mixed up
So here is the input:
5
10 3
20 5
15 6
15 1
10 2

and the output:
3
2 1 5

[prateekcaire]

You can treat each brick as 3 different bricks. A brick can be represented as (length x breadth x height). For example a brick of dimension 1x2x3 can be thought of 3 bricks as 1x2x3 or 2x3x1 or 3x1x2. Apply Longest increasing Sub sequence problem such that max height of tower can be obtained

Code: Select all

BS(index)
         if(index = 1) return h[1]
         if BS[index] return BS[index]   //memoization
         for each prevIndex from index-1 to 1
            if(l[index] <  length[prevIndex] && breadth[index] < breadth[prevIndex] && weight[index] < weight[previndex])
               max = BS(prevIndex) + height[index]
            if(BS[index] > max)
               BS[index] = max
               parent[index] = prevIndex


parent[] will hold the stacking info to create brick stack with max height

[poko]

Sorry maybe i told you it was a brick but it's a cube. So length=breadth=height.