演算法 Algorithm ─ Dynamic Programming 3

資源分配演算法

○ 依需求尋找最有效率的方法

    ※ 以工作&人力分配為例

範例：某公司接到5個project，公司人力只有3人，求最有效率的分配方式。

_______________________________________________________________________________
























○ 資源分配演算法的解法：
     
                             1. 先拆成N個部分 (project1、project2、project3、project4、project5)
                             2. 依序決定要投入的人力
                             3. 投入人力不得超過公司人力數
                             4.  圓圈(0,1) → 前面的0代表投入人力數、後面的1代表第1個project
                                  圓圈(1,3) → 前面的1代表投入人力數、後面的3代表第3個project       以此類推.....

    Tips： 線上的數字代表效率值


以最佳解法為例：   
                                   
         起點為圓圈S

            ● 1. 在project1 不投入任何人力，往圓圈(0,1)方向走

            ● 2. 投入1個人力在project2，效率值為5，往圓圈(1,2)方向走

            ● 3. 再投入1個人力在project3，效率值為9，往圓圈(2,3)方向走

            ● 4. 不在project4 不投入任何人力，往圓圈(2,4)方向走

            ● 5. 圓圈(2,4)要決定project5 是否要投入人力，但已無任何選擇所以投入1個人力在project5，

                   效率值為12，往圓圈T走，結束。

                                 
           

              所求得的最佳解為：
                                                  S→(0,1)→(1,2)→(2,3)→(2,4)→T
                                      
                                                   效率值為12