Hello!
Can someone help me to solve this problem? :/
"Soosk" has n candies, the i th candy with weight w[i]. He has a Merger machine that in each move receives two candies with weights X and Y, Then he pays X + Y dollars and the Merger makes a new candy with weight X + Y. Certainly after each Merge the number of candies decreases by one. Soosk wants to Merge all candies(in n-1 moves!) that in the end, he's paid the least possible amount of money.
1) What is the best algorithm for this problem?
2) If S = w[1] + w[2] + ... + w[n], how much money Soosk has to pay in the worst case?
3) If S = w[1] + w[2] + ... + w[n], what is average amount of money Soosk has to pay? (sorry for bad English)