AKSZ-背包
2024-06-30 17:05:46
发布于:广东
背包
01背包
设 dp[i][j]
表示在前 i 个物品中已经选好了最佳方案,并且容量不超过 j 时,所能获取的最大价值。
(对于任意一个 dp[i][j]
,已知 dp[1 ~ i - 1][1 ~ j - 1]
)
对于 i 物品,如果选择不装入,则有 dp[i][j] = dp[i - 1][j]
。
如果选择装入,则有 dp[i][j] = dp[i - 1][j - v[i]] + w[i]
。
两者取最大,则有 dp[i][j] = max(dp[i - 1][j], dp[i][j] = dp[i - 1][j - v[i]] + w[i])
。
初始化 dp[0][0 ~ V] = 0
,答案为 dp[T][V]
。
完全背包
状态设计同 01 背包
对于 i 物品,如果选择不装入,则有 dp[i][j] = dp[i - 1][j]
。
如果选择装入,则有 dp[i][j] = dp[i][j - v[i]] + w[i]
。
两者取最大,则有 dp[i][j] = max(dp[i - 1][j], dp[i][j] = dp[i][j - v[i]] + w[i])
。
初始化 dp[0][0 ~ V] = 0
,答案为 dp[T][V]
。
例题:
P1616 疯狂的采药
优化
滚动数组优化
对于状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i][j] = dp[i - 1][j - v[i]] + w[i])
。
可以发现只会使用到 dp[i]
和 dp[i - 1]
。
即可以将 dp[MAXM][MAXN]
优化为 dp[2][MAXN]
。
int dp[2][MAXN];
int now = 0, last = 1;
for(int i = 1; i <= M; i++)
{
now ^= 1, last ^= 1;
for(int j = 0; j <= T; j++)
{
if(j >= cs[i].t)
{
dp[now][j] = max(dp[last][j], dp[last][j - v[i]] + w[i]);
}
else
{
dp[now][j] = dp[last][j];
}
}
}
一维
对于上述滚动数组优化,可以注意到 dp[now][j]
的影响因素只有 dp[last][j]
和 dp[last][j - v[i]] + w[i]
。
所以只要更改 j 的枚举方向,便可以再次优化一维。
int dp[MAXN];
for(int i = 1; i <= M; i++)
{
for(int j = V; j >= V[i]; j--)
{
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
这里空空如也
有帮助,赞一个