背包问题之退背包

退背包就是从可选物品中删除其中一个物品，问满足所取总价值为 $j$j 的方案数。

像普通背包一样，退背包先普通dp以下，然后退去所选物品。

对于01背包，假设 $dp\left[i\right]$dp[i]​为未退背包前满足所取总价值为 $i$i​ 的方案数。 $d{p}^{\prime }\left[i\right]$dp′[i]​ 为退去第 $x$x​个物品后满足所取总价值为 $i$i​的方案数，那么 dp方程为

• 当 i<w[x]​时， $d{p}^{\prime }\left[i\right]=dp\left[i\right]$dp′[i]=dp[i]
• 当 $i\ge w\left[x\right]$i≥w[x]​时， $d{p}^{\prime }\left[i\right]=dp\left[i\right]-d{p}^{\prime }[i-w[x\left]\right]$dp′[i]=dp[i]−dp′[i−w[x]]​

代码表示：

for(int i=w[x];i<=m;++i) dp[i]-=dp[i-w[x]];

对于多重背包，假设 $dp\left[i\right]$dp[i]为未退背包前满足所取总价值为 $i$i 的方案数。 $d{p}^{\prime }\left[i\right]$dp′[i] 为退去第 $x$x个物品后满足所取总价值为 $i$i的方案数，那么 dp方程为

• 当 i<w[x]​时， $d{p}^{\prime }\left[i\right]=dp\left[i\right]$dp′[i]=dp[i]​
• 当 $i\ge w\left[x\right]$i≥w[x]时， $d{p}^{\prime }\left[i\right]=dp\left[i\right]-dp[i-w[x\left]\right]$dp′[i]=dp[i]−dp[i−w[x]]

代码表示：

for(int i=m;i>=w[x];--i) dp[i]-=dp[i-w[x]];

不难看出，其实这就是普通背包DP过程的逆过程。

相关题目：

The Preliminary Contest for ICPC Asia Shanghai 2019 J. Stone game :传送门