背包問題 (Knapsack)
場景:
某一設備最大工作量 W=10
今有待處理工作清單如下:
問題:
在設備最大工作量下,求取工作最大效益組合。
解法 1-貪婪法:
依每單位工作量之效益筆重製待處理工作清單如下:
工單排程如下:
工單4:累積工作效益=50,設備剩餘工作量=10 - 3 =7。
工單2:累積工作效益=50 + 40 = 90,設備剩餘工作量=7 - 4 =3。
結束 :其餘工單工作量均 > 3 ,超過設備負荷。
解法 2-動態規劃法:
工單排程如下:
選擇最大累積效益值 P2( 工單2 =4) = 90。
選擇 P1( 工單4 =3) 。
選擇路徑 = 工單4 工單2