0-1背包

背包容量为$ W $，物品有$N$个且每种物品不可重复使用，物品$n$的重量为$wg[n]$、价值为$val[n]$

问最多能装多少价值？

• dp数组定义
  $$dp[n][w] = 仅使用前n个物品（不可重复使用）、背包容量为w时能装下的最大价值$$

• 状态转移方程
  $$dp[n][w] = Max$$

有几种不同的装法

• 额外用一个三维数组path存放装法数量
  $$path[n][w] = 仅使用前n个物品（不可重复使用），背包容量为w时能装下最大价值的装法数量$$

• 状态转移方程
  $$&path[n-1][w] \quad 不装物品n \quad ① \
  &path[n-1][w-wg[n]] \quad 装入物品n \quad ②\[2ex]
  &path[n][w] =
  \begin{cases}
  ①, \quad ① > ②\[2ex]
  ②, \quad ①< ②\[2ex]
  ① + ②, \quad ①=②
  \end{cases}$$

具体装法

• 额外用一个三维数组path存放具体装法
  $$path[n][w] = 仅使用前n个物品（不可重复使用），背包容量为w时能装下最大价值的具体装法$$

• 状态转移方程

$$
path[n-1][w] \quad 不装物品n \quad ① \
path[n-1][w-wg[n] \quad 装入物品n \quad ② \[2ex]
path[n][w] =
\begin{cases}
① \quad①, \quad ①>② \[2ex]
②.EachOf().append(物品n) \quad②, \quad ①<②\[2ex]
[①, \quad ②.EachOf().append(物品n)], \quad ①=② \[2ex]
\end{cases}
$$

物品可重复使用

1. 修改dp数组定义为 可重复使用
2. 由于可以重复使用，状态转移方程 装入物品n 分支应该改为$dp[n][w-wg[n]]+val[n]$

完全背包

背包容量为$W$，物品有$N$个且每种物品可以重复使用，物品$n$的重量为$wg[n]$

问是否能够正好装满？

• dp数组定义
  $$dp[n][w] = 仅使用前n个物品（可重复使用），背包容量为w时是否能够正好装满$$

• 状态转移方程
  $$
  dp[n][w] = ||
  \begin{cases}
  dp[n-1][w]，不装物品n \[2ex]
  dp[n][w-wg[n]]，装入物品n
  \end{cases}
  $$

有几种不同的装法

1. 修改dp数组定义为 仅使用前n个物品（可重复使用），背包容量为w时正好能装满的装法数量
2. 状态转移方程改为 $dp[n][w] = dp[n-1][w] + dp[n][w-wg[n]] $

具体装法

1. 修改dp数组定义为 仅使用前n个物品（可重复使用），背包容量为w时正好能装满的具体装法（三维数组）
2. 状态转移方程改为 $dp[n][w] = [dp[n-1][w], \quad dp[n][w-wg[n]].EachOf().append(物品n)]$

物品不可重复使用

1. 修改dp数组定义为 不可重复使用
2. 状态转移方程 装入物品n 分支应该改为 $dp[n-1][w-wt[n]]$