背包九(三)讲
1. 01背包
问题描述
有 N 件物品和一个容量为 S 的背包。第 i 件物品的费用是 c[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
状态方程
$$
state[i][v] = max { state[i-1][v], state[i-1][v-c[i]]+v[i] }
$$
state[i][v]：只使用前 i 件物品，总花费刚好为 v 时的总价值
若包括第 i 个物品，则 state[i][v] = state[i-1][v-c[i]] + v[i]
若不包括第 i 个物品，则 state[i][v] = state[i-1][v]
最后要遍历 state[N-1][v], 最大的值即为答案
复杂度
时间复杂度：O(NS)
空间复杂度：O(NS)
优化后的状态方程
观察状态方程，state[i] 只用到了state[i-1] 的数据，可以压缩行数，相当于用 state[i] 的值覆盖 state[i-1]的值
$$
state[v] = max { state[v], state[v-c[i]]+v[i] }
$$
还是 i 从 0 到 N-1 遍历，只是 v 要从 S 到 0 遍历，在更新时前面的值对应 i-1 时的情况
最后要遍历 state[v]， 最大的值即为答案
优化后的复杂度
时间复杂度：O(NS)
空间复杂度：O(S)
2. 完全背包问题
问题描述
有 N 种物品和一个容量为 S 的背包，每种物品都有无限件可用。第 i 种物品的费用是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
状态方程
$$
state[i][v] = max { state[i-1][v-kc[i]]+kv[i] | 0 <= k*c[i] <= v }
$$
$$
state[i][v] = max { state[i-1][v], state[i][v-c[i]]+v[i] }
$$
tips：删掉这样的物品 a：存在物品 b，满足 c[b] < c[a] 且 w[b]/c[b] > w[a]/c[a]
复杂度
时间复杂度：>O(NS)
空间复杂度：O(NS)
优化后的状态方程
在遍历到 i 的时候，max() 的参数的 state[] 可能已经含有了物品 i
$$
state[v] = max { state[v], state[v-c[i]]+v[i] }
$$
i 从 0 到 N-1 遍历，v 要从 0 到 S 遍历
优化后的复杂度
时间复杂度：O(NS)
空间复杂度：O(S)
3. 多重背包问题
问题描述
有 N 种物品和一个容量为 S 的背包。第 i 种物品最多有 n[i] 件可用，每件费用是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
状态方程
可以把相同的物品当成01背包中不同的物品
转化出新的数组后：
$$
state[v] = max { state[v], state[v-c[i]]+v[i] }
$$
复杂度
时间复杂度：O( Σn[i]·S)
空间复杂度：O(S)
优化后的状态方程
优化前，n[i] 件相同的物品转化成 n[i] 个对应的值
用二进制思想，把 n[i] 件相同的物品转化成 logn[i] 个对应的值
例如，13 个相同的物品转化成 1 个费用 c[i]，价值 w[i] 的物品，加 1 个费用 2*c[i]，价值 2*w[i] 的物品，加 1 个 费用 4*c[i]，价值 4*w[i] 的物品，加 1 个费用 6*c[i]，价值 6*c[i] 的物品
优化后的复杂度
时间复杂度：O( Σlogn[i]·S)
空间复杂度：O(S)