背包 DP

施工中

介紹

背包博大精深，千萬不要覺得他很簡單，難死

簡單分類：

• 0/1 背包

• 無限背包

• 有限背包

• 分組背包

• 樹上背包

先分別來一點裸題

1. 0/1背包

2. 換位背包

3. Bitset加速背包

4. 有限背包 有二進制拆分跟單調隊列優化兩種做法，如果不那麼在意效率的話寫二進制就好了。但是在某些題目可能還是會用到 (ex: Bitset加速背包那題可以用單調隊列優化輾過去)

5. [分組背包] 這是樹上背包的基礎

6. 樹上背包 我放在樹DP那邊ㄌ

要注意的幾件事

1. 背包是DP，不要硬套

2. 無限背包沒想好就會變成有限背包，要小心

3. 應該還有 但是我想不到

例題

1. [CF 336C]

2. [LG 1954]

3. [LG 1858] 01背包前 k優解的價值和

4. [CF 864E]