[Solved]: Dynamic programming to find the least possible balance of a full binary tree

Problem Detail: 

I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an internal node $v$ is defined as the sum of weights of the leaves in the subtree rooted at $v$. The balance of an internal node is defined as the larger ratios of the weights of its two children. The balance of a tree is the maximum of the balances of its internal nodes.

I need to find the least possible balance of any full binary tree with $x_1,x_2,\cdots,x_n$ as the weights of its leaves. I don't need to output the tree, just the value.

I am having trouble finding the sub-problems. I have tried doing some examples, say the input is: $(5, 4, 3, 4, 4)$. I found the least possible balance of this to be $1.5$ by drawing all the possible trees. The tree that I ended up with is below and I put the balance beside each internal node:

For the example input, a smaller sub-problem would obviously be $(4,3,4,4)$, but I don't see how knowing the least possible balance of that helps me find the least possible balance of the tree with leaves $(5, 4, 3, 4, 4)$. I tried finding the balance for $(4,3,4,4)$ which came to be $1.33$. The tree I ended up with is:

I am looking for some hints as to what the sub-problems might be.

Asked By : user130554

Answered By : Leonardo Cotta

You should think about how your binary tree can be arranged. For each tree you have some nodes $x_1,\dots,x_k$ to the left and some $x_{k+1}, \dots, x_n$ to the right of the root. Now, the best possible imbalance for that root will be the arrangement that gives you the smaller ratio. So, you have to figure out a way of doing this evaluation in every internal node of your tree (considering the subtree rooted there). Another tip is to consider growing your tree while preserving the minimum imbalance. The "matrix-chain" problem is quite similar to this one, so you should take a look at it too. Good luck.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32912