01背包
有一个背包,最大负重为W;有n块宝石,每件宝石的价值为vi,重量为wi,i为[1,n]。求背包能装下的宝石的最大价值。
典型的动态规划问题。状态表为dp[i][j],i为[0,n],表示宝石的下标;j为[0,W],表示递增的总负重。其状态转移方程为:
dp[i,j] = dp[i-1][j], j < w[i];
dp[i,j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]), j >= w[i].
note: dp被初始化为全0数组。
代码
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= W; j++)
{
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
由于状态转移方程只用到了相邻行的状态,因此可以把状态表缩减成一维dp[j]。此时的状态转移方程为:
dp[j] = max(dp[j], dp[j-w[i]] + v[i]), j >= w[i]
note: j从W递减为1
代码
for (int i = 1; i <= N; i++)
{
for (int j = W; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
完全背包
有一个背包,最大负重为W;有n种宝石,每种宝石的价值为vi,重量为wi,i为[1,n]。宝石的数量无限。求背包能装下的宝石的最大价值。
状态表为dp[j],状态方程也是:
dp[j] = max(dp[j], dp[j-w[i]] + v[i]), j >= w[i]
但是j是从1递增至W,和上面的01背包相反。原因在于每种的宝石的数量都是无限的,是在解决当前问题(i种物品),向有i种物品的背包添加第i种物品;而01背包问题是在解决当前问题(i种物品),向有i-1种物品的背包添加第i种物品。
代码
for (int i = 1; i <= N; i++)
{
for (int j = w[i]; j <= W; j++)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
多维背包
有一个背包,最多能被Wa克a物质和Wb克b物质;有n种宝石,每种宝石的价值为vi,所含ab物质的质量分别为wai克和wbi克。求背包能装下的宝石的最大价值。
状态表为dp[j][k],状态方程为:
dp[j][k]=max(dp[j][k], dp[[j-wa[i]][[k-wb[i]] + vi)
for (int i = 1; i <= N; i++)
{
for (int j = Wa; j >= wa[i]; j--)
{
for (int k = Wb; k >= wb[i]; k--)
{
dp[j][k] = max(dp[j][k], dp[j - wa[i]][k - wb[i]] + v[i]);
}
}
}
可以扩展至任意维。
for (int i = 1; i <= N; i++)
{
for (int j = Wj; j >= wj[i]; j--)
{
for (int k = Wk; k >= wk[i]; k--)
{
for (int l = Wl; l >= wl[i]; l--)
{
...
dp[j][k][l]... = max(dp[j][k][l]..., dp[j - wj[i]][k - wk[i]][l - wl[i]]... + v[i]);
}
}
}
}
网友评论