There are n field stacks and the mass of i-th field stack is mi (mi > 0). Bob wants to merge
the n field stacks into only 1 stack. Every time Bob can merge one field stack with another
and the merging cost is the mass of two stacks. For example, there are 3 field stacks, and
their masses are m1 = 1, m2 = 2 and m3 = 4. You can merge m1 and m2 with the cost of
1 + 2 = 3, and then merge the new stack with m3, where the cost is 3 + 4 = 7, and the total
cost is 3 + 7 = 10.
Given the number of field stacks n and their masses mi, you should:
(a) Design a greedy algorithm to merge all field stacks with the lowest cost;
(b) Analyze the time complexity of your greedy algorithm;
(c) Prove the correctness of your algorithm;
(a) The greedy algorithm to merge all field stacks with the lowest cost can be described as follows:
1. Sort the field stacks in non-decreasing order based on their masses.
2. Initialize a variable `total_cost` to 0.
3. While there are at least two field stacks remaining:
- Merge the two field stacks with the lowest masses.
- Add the merged mass to `total_cost`.
- Remove the two merged field stacks from the list and insert the merged stack back into the list.
4. Return `total_cost` as the lowest cost to merge all field stacks.
(b) The time complexity of the greedy algorithm can be analyzed as follows:
1. Sorting the field stacks takes O(nlogn) time.
2. The merging operation is performed n-1 times because each merge reduces the number of field stacks by 1.
3. In each merging operation, finding the two lowest masses can be done in O(1) time if the field stacks are stored in a min-heap or sorted list.
4. Merging two field stacks and updating the total cost takes O(1) time.
5. Therefore, the overall time complexity of the greedy algorithm is O(nlogn), dominated by the initial sorting step.
(c) To prove the correctness of the greedy algorithm, we can use the exchange argument.
Let's assume that there is an optimal solution different from our greedy solution, where the field stacks are merged in a different order. We will show that we can exchange the order of merges to obtain a solution with the same or lower total cost.
Consider the first pair of field stacks that are merged differently in the optimal solution. Let's say the optimal solution merges field stack A and B, whereas our greedy solution merges field stack X and Y. Without loss of generality, assume the mass of A is greater than or equal to the mass of B, and the mass of X is greater than or equal to the mass of Y.
Since our greedy solution merges X and Y, we must have chosen X and Y as the two lowest masses available at that step. However, in the optimal solution, A and B were chosen instead. But since A >= B and X >= Y, the total cost of merging X and Y cannot be greater than merging A and B. Therefore, we can exchange the merge order and the total cost of our greedy solution will either remain the same or decrease.
By repeating this exchange argument for all pairs of merges in the optimal solution, we can conclude that our greedy solution is at least as good as the optimal solution, if not better.
Hence, the greedy algorithm provides an optimal (or equally optimal) solution to merge all field stacks with the lowest cost.