算法的原理:
范例:
有四位教授被分派開設四門課程,如何指派使所需的總准備時間為最小.已知個人對各 課程之准備時間如下表所示:
課程1
課程2
課程3
課程4
教授A 2 10 9 7 教授B 15 4 14 8 教授C 13 14 16 11 教授D 4 15 13 9解法:
Step 1. 在各列中找最小值,將該列中各元素檢去此值,對各行重復一次.
08 7 5 本列各減2
11 0 10 4 本列各減4
2 3 5 0本列各減11
0 11 9 5本列各減4
0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5本欄各減0
本欄各減0
本欄各減5
本欄各減0
Step 2. 檢驗各列,對碰上之第一個零,做記號,同列或同欄的其他零則畫X (由零較少 的列先做,可不依順序)
0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5
