几种背包问题
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