「Note」2022-06-23 拟阵贪心

…

$\mathbb{Definitions}$

拟阵是一个二元组，记拟阵 $\mathcal{M} = (U, \mathcal{I})$ ， 对于有限集 $U$ ，若 $\mathcal{I}$ 是 $U$ 上的一个集族(被称为独立集)。

前提条件有两个:

• 遗传性: $A' \subseteq A , A \in I \Rightarrow A' \in I$
• 交换性: $A \in \mathcal{I}, B \in \mathcal{I}, \mid A \mid < \mid B \mid \Rightarrow \exists x \in B, x \not\in A, x \cup A \in \mathcal{I}$

$\mathbb{Soluntion}$

若一个贪心求极值问题可以归为拟阵，则可以用以下的步骤求解。

$$ \begin{equation} \begin{aligned} &Greedy(M,w) \; \{ \\ &\;\;\;\;A \leftarrow \phi ; \\ &\;\;\;\;sort\,M_S\,into\,monotonically\,decreasing\,order\,by\,weight\,w; \\ &\;\;\;\;\textbf{while}\;(M_S \neq \phi)\; \{ \\ &\;\;\;\;\;\;\;\;x\leftarrow getMax(M_S);\\ &\;\;\;\;\;\;\;\;\textbf{if} \;(A \cup \left \{ x \right \} \in M_l)\\ &\;\;\;\;\;\;\;\;\;\;\;\;A\leftarrow A \cup \left \{ x \right \};\\ &\;\;\;\; \} \\ &\;\;\;\;\textbf{return}\;A;\\ &\} \end{aligned} \end{equation} $$

其实就是个理论基础。只要满足上面两个性质，就能贪心。