背包问题

背包问题: 一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

假设我们有$n$种物品，每种物品的重量为$w_i$，价值为$v_i$，背包的容量为$C$。我们的目标是找到一种方案，使得背包中物品的总价值最大。

根据问题的不同，背包问题可以分为以下几种：

\[max \sum_{i=1}^{n} v_ix_i \quad\] \[s.t. \sum_{i=1}^{n} w_ix_i \leq C , x_i \in \{0,1\}\]

定义$f(i, j)$为前只选择编号为$1,2,…,i$的物品，背包容量不超过$j$的情况下，能够拿取物品的最大价值。则有状态转移方程：

\[f(i, j) = max(f(i-1, j), f(i-1, j-w_i) + v_i)\]

$f(i-1,j)$表示不选择第$i$个物品能获得的最大价值，$f(i-1, j-w_i)$表示选择第$i$个物品后，背包剩余容量为$j-w_i$时能获得的最大价值。

由于$f(i, j)$只依赖于$f(i-1, j)$和$f(i-1, j-w_i)$，因此可以使用滚动数组优化空间复杂度。

即

\[f(j) = max(f(j), f(j-w_i) + v_i)\]

但遍历j的时候，需要从大到小遍历，因为$f(j)$依赖于$f(j-w_i)$，如果从小到大遍历，$f(j-w_i)$的值已经被更新为$max(f(j-w_i), f(j-w_i-w_i) + v_i)$，这样相当于多选第$i$个物品。

\[max \sum_{i=1}^{n} v_ix_i \quad\] \[s.t. \sum_{i=1}^{n} w_ix_i \leq C , x_i \in \{0,1,2,3,...\}\]

定义$f(i, j)$为前只选择编号为$1,2,…,i$的物品，背包容量不超过$j$的情况下，能够拿取物品的最大价值。则有状态转移方程：

\[f(i, j) = max(f(i-1, j), f(i, j-w_i) + v_i)\]

$f(i-1,j)$表示不选择第$i$个物品能获得的最大价值，$f(i, j-w_i)$表示选择第$i$个物品后，背包剩余容量为$j-w_i$时能获得的最大价值。

注意这里和0-1背包问题的区别，0-1背包问题是$f(i, j) = max(f(i-1, j), f(i-1, j-w_i) + v_i)$，而完全背包问题是$f(i, j) = max(f(i-1, j), f(i, j-w_i) + v_i)$。因为完全背包问题可以选择多次第$i$个物品。

同样可以使用滚动数组优化空间复杂度。

\[f(j) = max(f(j), f(j-w_i) + v_i)\]

但遍历j的时候，需要从小到大遍历，因为$f(j)$依赖于$f(j-w_i)$。

\[max \sum_{i=1}^{n} v_ix_i \quad\] \[s.t. \sum_{i=1}^{n} w_ix_i \leq C , 0 \leq x_i \leq n_i\]

可以将多重背包问题转化为0-1背包问题，将第$i$种物品拆分为$n_i$个物品，每个物品的重量和价值都是原来的$w_i$和$v_i$。