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

• 背包九讲

• 背包九讲专题 | 大雪菜