dynamic-programming note (动态规划专题)

## 关于0/1 Knapsack Problem 的思考过程

### 数据规模和约定

$1<=N<=200,M<=5000.$

## 首先是状态转移方程

$N$ 物品的件数
$Ni$ 第 $i$ 件物品
$V$ 背包的总容量
$v$ 当前背包的容量
$Ci$ 第 $i$ 个物品消耗的容量
$Wi$ 第 $i$ 个物品获取的价值

## 算法设计和实现

### 空间复杂度$O(NV)$

$v→V$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
$Ni$ $Ci$ $Wi$ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 5 0 0 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
2 3 7 0 0 5 7 7 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12
3 6 4 0 0 5 7 7 12 12 12 12 12 12 16 16 16 16 16 16 16 16 16 16
4 3 8 0 0 5 8 8 13 15 15 20 20 20 20 20 20 24 24 24 24 24 24 24
5 4 5 0 0 5 8 8 13 15 15 20 20 20 20 25 25 25 25 25 25 29 29 29

## 实现代码

Author: Junzhou Liu