背包问题总结

0-1背包问题

一个旅行者最多能装M公斤的背包，现有n件物品，它们的重量分别是$W_1,W_2\cdots W_n$,它们的价值分别是$C_1,C_2\cdots C_n$.求旅行者能获得的最大价值

二维dp方程

另dp[i][j]为当前处理到第i个物品，且背包已装入小于等于j容量后的最大价值。guess第i个物品是否装入：

• 当j<w[i],第i个物品一定无法装入。于是dp[i][j] = dp[i-1][j]
• 当j>=w[i],第i个物品可装入也可不装入，于是
  $dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]])+c[i]$

一维dp

上述二维方程显然i只和i-1有关。因此可以设置pre和next数组将空间复杂度优化成一维。即$next[j]=max(pre[j],pre[j-w[i]]+c[i])$

滚动数组优化

注意上述一维dp中，next数组的j位置仅与pre的j之前的元素有关。假设现在的next已经是pre了，我们要求下一个next。可以考虑逆向推导。即$next[j]=max(next[j],next[j-w[i]]+c[i])$，j从大到小遍历（这使得括号里的为上一时间步的值）

完全背包问题

一个旅行者最多能装M公斤的背包，现有n种物品，它们的重量分别是$W_1,W_2\cdots W_n$,它们的价值分别是$C_1,C_2\cdots C_n$.每种物品都有无限件。求旅行者能获得的最大价值。

类似0-1背包问题的dp

令dp[i][j]为当前处理到第i个物品，且背包已装入小于等于j容量后的最大价值。guess第i个物品装入多少个，显然最多可能装入j/w[i]个，最少则不装入。
则为求dp[i][j],需要对每个$0\le k\le j/w[i]$,更新$dp[i][j]=max(dp[i][j],dp[i-1][j-k\cdot w[i]]+k\cdot c[i])$。
则填表后可能导致$O(mnk)$的复杂度。有无可能更优化呢？

二维dp方程

不要定势思维地想从前缀进行状态转移。注意每个物品都有无限个，若只考虑前i个物品，我们可以guess第i个物品是否至少装入一个来更新上述dp方程：$dp[i][j]=max(dp[i][j-w[i]]+c[i],dp[i-1][j])$。则填表复杂度$O(mn)$
该方法较上种做法更好，是由于本身我们在求$dp[i][j-w[i]]$时，已经对一部分k求出了最大值了，不必重复计算。$dp[i][j-w[i]]$对应的装法也可以进一步地装入第i个物品，直到可以在某次取到$dp[i-1][j-k\cdot w[i]]$。这和上种方法的计算是等价的。

一维dp

方式和0-1背包问题相同

滚动数组优化

$next[j]=max(next[j],next[j-w[i]]+c[i])$，只不过j是从小到大遍历。

多重背包问题

一个旅行者最多能装M公斤的背包，现有n种物品，它们的重量分别是$W_1,W_2\cdots W_n$,它们的价值分别是$C_1,C_2\cdots C_n$.第i件物品有$n[i]$件。求旅行者能获得的最大价值。

类似0-1背包问题的dp

和上述做法一致。只不过k上界是min(j/w[i],n[i])
$dp[i][j]=max(dp[i][j],dp[i-1][j-k\cdot w[i]]+k\cdot c[i])$

二进制优化（very good）

上述做法并未充分利用每种物品之间相同的条件
就是说上述做法完全是按0-1背包问题的套路，上述做法也可以在相同的时间复杂度内做出相同件彼此间互不同物品的问题
对同一种物品，我们可以构造$O(\log n)$种不同物体，这些物体的不同组合对应原始物品取得不同件数。

• 对物体1，假设其由1件该种类物品组成。
• 对物体2，假设其由2件该种类物品组成。
• 对物体3，假设其由4件该种类物品组成。

余下不够2的次幂的将其视作一个物体。对每种物品都分别构造物品。
于是将问题转换为在物体上的0-1背包问题。当然空间复杂度会稍微高一点了。

二维背包问题$knapsackProblem$

N件物品和容量是V的背包，背包能够承载的最大重量为M。每件物品只可以使用以此，体积是$a_i$,重量是$b_i$，价值是$w_i$，求将哪些物品装入背包，可使得物品的总提及不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。求出这个最大价值。

二维dp

设dp[i][j][k]为考虑前i个物品，体积至多为j，重量至多为k时的最大价值。

$$dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-a[i]][k-b[i]]+w[i])$$

对每个i，循环遍历j与k填表

滚动数组优化

$$dp[j][k]=max(dp[j][k],dp[j-a[i]][k-b[i]]+w[i]))$$
从左向右，从下到上填写即可。