章節連結
重念一次早該補起來的「資料結構與演算法」。這篇筆記下背包 Knapsack Problem 問題。
![[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74](https://smlpoints.com/wp-content/uploads/notes-theideaofalgorithm-javascript-1.jpg "[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74")
課程相關資訊
[連結]：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 的值變得比原本還小，那就表示這不是一個好的拿法，那就不往後考慮了
