题解:消失之物

算法

地址：https://www.luogu.com.cn/problem/P4141

Published

January 22, 2022

Content note — Known errors · 明显错误

消失之物的文字转移方程边界写错，和后面的代码不一致。

文中写 j-v[i] > 0，代码和背包语义应处理 j >= v[i]。
公式里的 g[i-1][j-v[i]] 与滚动数组推导不一致，建议重新推导。

题解 : 消失之物

1.题意:

地址：https://www.luogu.com.cn/problem/P4141

ftiasch 有 n 个物品, 体积分别是 $w_1,w_2,\dots,w_n$。由于她的疏忽，第 i个物品丢失了。

“要使用剩下的 n-1 物品装满容积为 x 的背包，有几种方法呢？”——这是经典的问题了。

她把答案记为 $\text{cnt}(i,x)$ ，想要得到所有$i \in [1,n], x \in [1,m]$ 的 $\text{cnt}(i,x)\%10$ 表格。

2.思路：

很显然，可以轻松地求出使用所有物品装满容积 j 的方案数

$f[i][j]$表示使用前 i 个物品的容积为 j 的背包方案数

令$g[i][j]$表示不使用第 i 个物品的容积为 j 的背包方案数

· 1.当$j-v[i] > 0$ 的时候，$f[i][j]$ 必然会包含选取了第 i 个物品所构成的一些方案，且在这些情况中，第 i 个物品必然只存在一个。那么，在$f[i][j] $中的这些状态必然是从$g[i][j-v[i]]$(不选i装满容积j-v[i])的状态下再拿了一个 i 构成的。

· 2.当$j-v[i]\leq0$的时候，$f[i][j]$ 中本来就不包含选取 i 这个物品的情况所以直接就是$f[i][j]$ 。

转移方程为： \[ H(f)=\left\{\begin{matrix} g[i][j]=f[n][j]-g[i-1][j-v[i]]，j-v[i]>0\\ f[i][j]，j-v[i]\leq0 \end{matrix}\right. \] 最后加上滚动数组优化就好了

3.代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=3e3+7;
int f[MAXN],g[MAXN],v[MAXN];
template <typename _TP>
inline void qread(_TP &X){
    char ch=0;int w;X=0;
    while(!isdigit(ch)){w=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
    X=w?-X:X;
}
int main(){
    int n,m;
    qread(n);qread(m);
    for(int i=1;i<=n;i++){
        qread(v[i]);
    }
    f[0]=1;g[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=(f[j]+f[j-v[i]])%10;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j>=v[i])g[j]=(f[j]-g[j-v[i]]+10)%10;
            else g[j]=f[j];
            cout<<g[j];
        }
        cout<<"\n";
    }
    return 0;
}