几种背包问题
01背包问题
有\(N\)个物品和一个容量是\(V\)的背包。
第\(i\)个物品的体积是\(vi\)，价值是\(wi\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
对于每件物品，要进行决策是否装入背包。
因为每件物品只有取和不取两种状态，所以叫做01背包问题
动态规划转移方程：
f[i][j] = max{f[i-1][j] , f[i-1][j-v[i]] + w[i]}
其中i表示前i件物品，j表示当前背包容量为j时。
-
背包装不下第\(i\)件物品，则
f[i][i] = f[i-1][j] -
背包装得下，如果不选第\(i\)件物品，则
f[i][i] = f[i-1][j] -
背包装得下，选第\(i\)件物品，
f[i][i] = f[i-1][j-v[i]] + w[i]
循环应该这样写：
for (int i=1;i<=N;i++)
{
for (int j=1;j<=V;j++)
{
if (j < v[i]) f[i][j] = f[i-1][j];
else f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i]])
}
}
边界问题：
f[0][0] = 0 即0件物品时价值为0
01背包问题优化
因为每一次的 \(i\) 只需要从 \(i-1\) 状态更新，所以可以压缩为一维数组。
f[j] = max(f[j],f[j-v[i]] + w[i]])
同时要将 \(j\) 循环倒序，因为 \(j-v[i]\) 是严格小于 \(j\) 的，倒序可以让每个状态 \(i\) 都是由上一层 \(i-1\) 的状态更新
即for (int j=V;j>=0;j--)
完全背包问题
在01背包问题的基础上，让每件物品可以取无限次。
动态规划转移方程：
f[i][j] = max{f[i-1][j] , f[i][j-v[i]] + w[i]}
与01背包问题不同的只有后面那一项中的i变为了i-1
数学推导：
\[①f[i][j] = max(f[i-1][j] , f[i-1][j-v] + w , f[i-1][j-2v]+2w,f[i-1][j-3v]+3w,...f[i-1][j-kv]+kw) \] \[②f[i][j-v] = max(f[i-1][j-v] , f[i-1][j-2v] + w , f[i-1][j-3v]+2w,f[i-1][j-4v]+3w,...f[i-1][j-(k+1)v]+kw) \]可以发现，\(②\) \(+w\) 是 \(①\) 式中\(f[i-1][j]\)右边的式子
所以
\[f[i][j] = max(f[i-1][j] , f[i][j-v] + w) \]循环应该这样写：
for (int i=1;i<=N;i++)
{
for (int j=1;j<=V;j++)
{
if (j < v[i]) f[i][j] = f[i-1][j];
else f[i][j] = max(f[i-1][j],f[i][j-v[i]] + w[i]])
}
}
完全背包问题优化
f[j] = max(f[j],[j-v[i]] + w[i]])
但此时不需要 \(j\) 循环倒序，因为每次更新第 \(i\) 层也是从第 \(i\) 层来的，也就是上面的f[i][j-v[i]]
多重背包问题
第 \(i\) 种物品最多有 \(si\) 件，每件体积是 \(vi\)，价值是 \(wi\)。
在01背包问题的基础上，让每件物品可以取一定次数。
动态规划转移方程 (已优化) ：
f[j] = max{f[j] , f[j-k*v[i]] + k*w[i]} (k >= 0 && k <= s && k * v <= j)
在范围内枚举 \(k\) 的取值
多重背包问题的二进制优化：
思想：对于每一种物品，可以取0~k个，把取的每一种看做一个新的物品，体积是k*v，价值是k*w，又因为每一个数都可以用二进制形式表示，即0~k之间的任何一个数都可以拆成2的次方和形式。所以，枚举这k个物品，只用枚举\(\log_{2}{k}\)个物品。后面的操作就和01背包问题相同了。
标签：件物品,01,max,问题,背包,物品 From： https://www.cnblogs.com/juniexd/p/17015527.html