# Knapsack

The knapsack problem is a typical DP problem.

## Type

1. 0-1 Knapsack (01背包问题. 每个物品最多选一次)
2. Unbounded Knapsack (完全背包问题. 每个物品可以选无限次)
3. Bounded Knapsack (多重背包问题. 每个物品可以选有限次)
4. 混合背包问题 (每个物品能选取的次数可能是1次, 有限次或者无限次)
5. 二维费用背包问题
6. 分组背包问题 (同一组内的物品只能选一个)
7. 背包问题求方案数
8. 求背包问题的方案
9. 有依赖的背包问题

## Reference

* [背包九讲](https://github.com/tianyicui/pack)
* [背包九讲专题 | 大雪菜](https://www.bilibili.com/video/BV1qt411Z7nE)