Introduction
It is hard level algorithm. I spent over 30 minutes to write a greedy algorithm. I like the experience and also it is good idea to write a blog for the practice.
Greedy algorithm
The greedy algorithm does not work. The counter example is [6, 4, 4, 6]. The greedy algorithm will start from [4, 4] to merge one pile, and then [8, 6], and then [6, 14]. The total cost will be 42. The minimum cost can be generated by not greedy algorithm, starting from [6, 4] to merge one pile 10, and then [6, 4] to merge to one pile 10, and then [10,10] is merged to one pile 20, the total cost will be 40.
Here is my greedy algorithm code.
How to divide into subproblems?
Based on the example [6, 4, 4, 6], K = 2. There are the following three subproblems to solve.
case 1:
subproblem: array [6, 4, 4], K = 2 -> to K -1 piles
subproblem: array [6], K = 2 -> to one pile
[6, 4, 4] to merge into one pile, the minimum cost will be 6 + [4, 4] to one pile, 6 + 8 + 8 = 22. So we can conclude that case 1's cost will be 50.
case 2:
subproblem: array [6, 4], K = 2 -> to K - 1 piles
subproblem: array [4, 6], K = 2 -> to one pile
case 2's cost will be 40.
case 3:
subproblem: array [6], K = 2 -> to K - 1 piles
subproblem: array [4, 4, 6], K = 2 -> to one pile
case 3's cost will be 50.
So the minimum cost will be minimum ( case 1, case 2, case 3).
No comments:
Post a Comment