[演算法 Day2]

本次的課程內容:重要的五大問題

解決問題簡單,定義問題困難

  • Status of each person:
    >> free (unmarried) ~engaged(訂婚但可毀約)~married [Shapley]
1. initialize each person to be free
2. while (some man m is free and hasn't proposed to every woman)do
3. w = highest ranked woman in m's list to whom m has not yet proposed
4. if (w is free) then
5. (m,w) become engaged
6. else if (w prefers m to her fiance m') then
7. (m,w) become engaged
8. m' become free
9. return the set S of engaged pairs

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store