i wrote a different proof for the box sorting algorithm in O(n^2) and proved it by induction.
can someone please refute/provide another proof to the solution?
The Problem-
You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). all the lengths are different, and widths are different.You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.you can NOT rotate a box so that any side functions as its base.
the known solution-
Sort the boxes by ascending base area . Create a table t of size n indexed by 1 ≤ i ≤ n. Starting with i = n to 1, define t[i] by max { h(i) , max { h(i) + t[j]} for all j>i such that w(j)>w(i) and l(j)>l(i)} Return the following value: max {t[1], . . . , t[n]} my solution -
sort the boxes by ascending width in array W, and by ascending length in array L. create a nxn matrix, where t[i,j] = tallest possible stack built on a L(i) long and W(j) wide base. the answer will be in t[n,n] since that is our max possible base area. for the first row in the matrix (this is the tallest stack that can be built on the minimum length base area - meaning only the box with the minimum length can be in it)
define t[1,j]:
0 <-- if W(j) < width of the box with min length
height of the box with lowest length <-- if W(j) >= width of the box
for the first column in the matrix (this is the tallest stack that can be built on the minimum width base area - meaning only the box with the minimum width can be in it)
define t[i,1]:
0 <-- if L(i) < length of the box with min width height of the box with lowest width <-- if L(i) >= length of the box with min width define t[i,j] = height of the box whose length is L(i) and width is W(j) , if such exist + max { t[i-1,j] , t[i,j-1] }
there can only be one box with those attributes since they are all unique. thank you all!