IS CS-2023S-02

题目来源：Problem 2 日期：2024-08-17 题目主题: CS-算法-贪心算法与复杂度分析

解题思路

这道题目主要涉及集合的划分问题，并用贪心算法对一个优化问题进行求解。我们需要解决的核心问题是如何最小化在集合划分过程中最大子集和的最大值。为了回答这道题目中的几个小问，我们会利用贪心算法的性质以及数学分析方法。

Solution

Question 1: Calculate $\mathrm{minmaxsum}(\{3,4,5,6\},2)$

To find $\mathrm{minmaxsum}(\{3,4,5,6\},2)$, we need to find the optimal way to divide the set $\{3,4,5,6\}$ into two subsets such that the maximum subset sum is minimized.

The total sum of the set $P$ is:

$$\Vert \mathbf{P}\Vert =3+4+5+6=18$$

We need to divide this into two subsets such that the maximum sum is as small as possible. We can consider the following possible divisions:

• $P_1=\{3,6\},P_2=\{4,5\}$:

  • $\Vert {\mathbf{P}}_1\Vert =3+6=9$
  • $\Vert {\mathbf{P}}_2\Vert =4+5=9$
  • Maximum sum = 9

• $P_1=\{3,5\},P_2=\{4,6\}$:

  • $\Vert {\mathbf{P}}_1\Vert =3+5=8$
  • $\Vert {\mathbf{P}}_2\Vert =4+6=10$
  • Maximum sum = 10

• $P_1=\{3,4\},P_2=\{5,6\}$:

  • $\Vert {\mathbf{P}}_1\Vert =3+4=7$
  • $\Vert {\mathbf{P}}_2\Vert =5+6=11$
  • Maximum sum = 11

The minimum maximum sum among these divisions is 9. Therefore:

$$\mathrm{minmaxsum}(\{3,4,5,6\},2)=9$$

Question 2: Show $\mathrm{minmaxsum}(P,m)\ge \Vert \mathbf{P}\Vert /m$

Let $P=\{x_1,x_2,\dots ,x_n\}$, and suppose we divide $P$ into $m$ subsets $P_1,P_2,\dots ,P_m$. By definition:

$$\mathrm{minmaxsum}(P,m)=\underset{Q}{\min }\underset{i}{\max }\Vert {\mathbf{P}}_i\Vert$$

where $Q$ is a possible division of $P$ into $m$ subsets.

For any division $Q$, the sum of all elements in $P$ must equal the sum of the elements in all subsets:

$$\sum _{i=1}^m\Vert {\mathbf{P}}_i\Vert =\Vert \mathbf{P}\Vert$$

Let $M={\max }_i\Vert {\mathbf{P}}_i\Vert$. Then:

$$m\cdot M\ge \Vert \mathbf{P}\Vert$$

because the total sum is distributed across $m$ subsets, and the largest subset sum must be at least $\Vert \mathbf{P}\Vert /m$:

$$M\ge \frac{\Vert \mathbf{P}\Vert }{m}$$

Since $\mathrm{minmaxsum}(P,m)$ is the minimum possible value of $M$, we have:

$$\mathrm{minmaxsum}(P,m)\ge \frac{\Vert \mathbf{P}\Vert }{m}$$

Question 3: Show that $\mathrm{approx}\text{-}\mathrm{minmaxsum}(P,m)\le 2\cdot \mathrm{minmaxsum}(P,m)$

The algorithm attempts to balance the largest and smallest subset sums by moving the top element from the stack with the largest sum to the stack with the smallest sum until no improvement can be made.

Let $M=\mathrm{minmaxsum}(P,m)$. Initially, each subset in the division $Q$ has a sum less than or equal to $M$.

When the algorithm moves an element from the subset with the largest sum to the subset with the smallest sum, the maximum possible increase in the smallest sum is bounded by the value of the largest element moved. This adjustment ensures that the final maximum sum $M_f$ in the approximate solution satisfies:

$$M_f\le M+M\le 2M$$

Thus:

$$\mathrm{approx}\text{-}\mathrm{minmaxsum}(P,m)\le 2\cdot \mathrm{minmaxsum}(P,m)$$

Question 4: Show that the while loop in the above code will be repeated at most $n$ times, regardless of whatever division $Q$ is chosen in line 2

Each iteration of the while loop in the pseudo-code moves an element from the stack $S_j$ (which has the maximum sum) to the stack $S_k$ (which has the minimum sum). Since the total number of elements in all stacks is $n$, and each move reduces the number of elements in $S_j$ by one, the maximum number of iterations cannot exceed $n$. After $n$ moves, the stacks have been exhausted of elements that can be moved:

$$\text{Number of while loop iterations }\le n$$

Question 5: Describe data structures needed to make the above algorithm run in $O(n\log m)$ time, and explain how to use them

To achieve an $O(n\log m)$ runtime, we can use a priority queue (or a binary heap) for efficiently finding and updating the stacks with the maximum and minimum sums. The steps are as follows:

1. Initialize: Use two priority queues, one for the stack with the maximum sum and one for the stack with the minimum sum.

   • Insert each stack’s sum along with its identifier into the respective priority queues. Both insertion and deletion in a priority queue take $O(\log m)$ time.

2. Update: During each iteration of the while loop:

   • Extract the maximum from the “max” priority queue and the minimum from the “min” priority queue.
   • Perform the pop operation from the stack with the maximum sum and push the element onto the stack with the minimum sum.
   • Update the priority queues with the new sums. This step also takes $O(\log m)$ time.

Since each operation inside the while loop is $O(\log m)$, and the loop runs at most $n$ times, the total time complexity of the algorithm is $O(n\log m)$.

知识点

贪心算法集合划分复杂度分析

重点词汇

• division: 划分
• priority queue: 优先队列
• minmax: 最小最大化

参考资料

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 16: Greedy Algorithms.
2. Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson. Chapter 6: Greedy Algorithms.