章節連結
重念一次早該補起來的「資料結構與演算法」。這篇筆記下背包 Knapsack Problem 問題。
課程相關資訊
[連結]:https://hiskio.com/courses/572/lectures/29991
本篇範圍:Chapter 12
請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。
內容
0 / 1 背包問題
找到放入或是不放入,使所得最大化的類型。
可以使用 Branch and bond、暴力解或是 backTracking
暴力解
全部的解法一共會有 2^n 種。例如有 5 個東西要做取捨,全部的選法就是 2^5 = 32。
BackTracking
從暴力解衍生,結果其實產生了一組完整的 Binary Tree。中間的過程都可以當成一個節點,如果中途有違反的,那就可以回朔上一層直到根節點為止。
Branch and Bound
1. 先算出每一個 Item 的 Profit / Weight 的值
2. c -> 若將題目當做 Fractional 問題,所能得到的值
3. lowerbound -> 以最簡單的方式,能獲得的最小利潤
lowerbound 會是變動的。如果你的 lowerbound 的值變得比原本還小,那就表示這不是一個好的拿法,那就不往後考慮了