考虑这样一个问题：有 $n$ 个物品，体积分别是 $w_1,w_2,\cdots,w_n$，背包容量为 $m$，共有 $n$ 次询问，第 $i$ 次询问要求不选物品 $i$ 时共有多少选法装满背包。

如果对于每个询问依次求 01 背包问题，单次询问需要 $O(nm)$ 的时间，总复杂度 $O(n^2m)$。而退背包能让我们不需要对于每个询问都进行完整的 DP，而是用 $O(m)$ 时间去掉选择了物品 $i$ 的方案数，那么整个过程需要一次 $O(nm)$ 的DP和 $n$ 次 $O(m)$ 的退背包/加背包过程，整体复杂度就降到了 $O(nm)$。

1. 执行一次 01 背包算法过程

for(int j=m;j>=w[i];--j)
    f[j]+=f[j-w[i]];

1. 对每个物品，将其看作是最后一个加入背包的物品，然后减掉它的方案数

memcpy(g,f,sizeof f);
for(int j=w[i];j<=m;++j)
    g[j]-=g[j-w[i]];

洛谷 P4141 消失之物

有 $n$ 个物品，体积分别是 $w_1,w_2,\cdots,w_n$，现第 $i$ 个物品丢失，用剩下的 $n-1$ 个物品装满容积为 $x$ 的背包，有几种方法。把答案记为 $cnt(i,x)$，要得到所有 $i\in[1,n],x\in[1,m]$ 的 $cnt(i,x)$ 表格。输出 $n\times m$ 的矩阵，表示 $cnt(i,x)$ 的末位数字。

$1\le n,m\le 2000$。

令 $f[j][0]$ 表示不算消失的物品组成容积为 $j$ 的方案数，即 01 背包问题，令 $f[j][1]$ 表示删掉某个物品后组成容积为 $j$ 的方案数。初始化是 $f[0][0]=f[0][1]=1$，即容积为 0 时方案数为 1

<查看代码 hidden>

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int f[N][2],w[N];
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    f[0][0]=f[0][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            f[j][0]=(f[j][0]+f[j-w[i]][0])%10;
        }
    }
 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j-w[i]>=0) f[j][1]=(f[j][0]-f[j-w[i]][1]+10)%10;
            else f[j][1]=f[j][0]%10;
            printf("%d",f[j][1]);
        }
        puts("");
    }
    return 0;
}

</hidden>