NikaraBika's blog

"Merge candies" Problem
By NikaraBika, 10 years ago, In English

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)

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Every step merge two the lightest candies.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tnx very much :) Can you answer the other parts of this problem plz?

    → Reply