贊助廠商

娛樂城推薦

首頁

刊登資訊

  • 刊登者:匿名
  • 時間:2021-06-09 12:10:05

尚未解答計算數學 Problem Solving- 01背包的暴搜有甚麼特別的剪枝嗎?

計算數學 Problem Solving- 01背包的暴搜有甚麼特別的剪枝嗎?

01背包是假多項式

背包容量超大時無法DP

只能用branch and bound

一般教科書上提到的剪枝的方法:

把物品依照CP值排序 CP值高的先放進去

用貪心法計算upper bound

upper bound比較大的點優先擴展

想請問各位大大

還有甚麼特別的方法可以加速嗎?


小弟在修演算法的課

卡一筆測資1000個物品 容量又超大

感謝


--

0個答案 計算數學 Problem Solving- 01背包的暴搜有甚麼特別的剪枝嗎?

其他問題

友站連結