Can we solve this question using greedy approach, the way we used it in rope joining problem?
At any time we will take two minimum elements(let’s say a and b), replace them with a single element equal to sum of the two elements(a+b). we will increment result(smoke generated) by a*b
Can greedy be used?
No it cannot be solved using greedy approach as many paths exist for a given set of input. And we want to choose the best possible path. For example -
40 60 20
We can mix first and second mixture first resulting in a smoke of 2400 and mixtures become - 0 20
These two will result in a smoke of 0 and final answer is 2400.
In the other path if we move greedily and mix second and third mixtures first, smoke generated will be 1200 and mixtures will be - 40 80. These will further add a smoke of 3200.
Total smoke generated will be 4400 which is much more than previous one.
So greedy solution will not work here.