首頁‎ > ‎演算法‎ > ‎

背包問題 (Knapsack)

場景

  • 某一設備最大工作量 W=10
  • 今有待處理工作清單如下:

    工單編號 i 1 2 3 4
    設備工作量 wi 5 4 6 3
    工作效益 vi 10 40 30 50

問題

  • 在設備最大工作量下,求取工作最大效益組合。

解法 1-貪婪法

依每單位工作量之效益筆重製待處理工作清單如下:

工單編號 i 4 2 3 1
設備工作量 wi 3 4 6 5
工作效益 vi 50 40 30 10
工作效益比 ri 50/3 10 5 2

工單排程如下:

  1. 工單4:累積工作效益=50,設備剩餘工作量=10 - 3 =7。
  2. 工單2:累積工作效益=50 + 40 = 90,設備剩餘工作量=7 - 4 =3。
  3. 結束  :其餘工單工作量均 > 3 ,超過設備負荷。

解法 2-動態規劃法

工單排程如下:

  1. 選擇最大累積效益值 P2( 工單2 =4) = 90。
  2. 選擇 P1( 工單4 =3) 。
  3. 選擇路徑 =  工單4 工單2

ċ
Knapsack-Formula.txt
(1k)
李智,
2012年9月8日 上午7:18