本题为$01$背包的一个拓展。
我们知道,$01$背包的状态转移方程是f[j]=max(f[j],f[j-v[i]]+w[i])
这时,我们要对其进行分类讨论,不重不漏地分为3类:

• $f[j]>f[j-v[i]]+w[i]$ 此时$f[j]$不变,$g[j]=g[j]$
• $f[j]<f[j-v[i]]+w[i]$ 此时$f[j]=f[j-v[i]]+w[i]$,$g[j]=g[j-v[i]]$
• $f[j]==f[j-v[i]]+w[i]$ 此时$f[j]=f[j]=f[j-v[i]]+w[i]$,$g[j]=g[j]+g[j-v[i]]$

了解了这个,我们看看这道题的两种做法:

第一种:

//这种做法f[i][j]的所有选法总体积恰好为j

#include<bits/stdc++.h>
using namespace std;

const int N = 1010,mod=1e9+7;
int f[N];//f[i][j]:从前i个物品中选,总体积恰好等于j的所有选法的价值最大值
int g[N];//g[j]:体积恰好为j的最优选法数量
int n,m;

int main()
{
    cin>>n>>m;

    memset(f,-0x3f,sizeof f);//全部设为负无穷,以确保用来更新f的f[j]总体积都是满的
    f[0]=0;
    g[0]=1;

    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {   
            // 这里的maxv很妙,巧妙地用简洁的代码概括了3种情况
            int maxv,s=0;
            maxv=max(f[j],f[j-v]+w);

            if(f[j]==maxv)s+=g[j]%mod;
            if(f[j-v]+w==maxv)s=(s+g[j-v])%mod;

            g[j]=s,f[j]=maxv;
        }
    }

    int maxv=0,idx;
    for(int i=0;i<=m;i++)//因为状态表示是体积恰好为j,所以最大值不是f[m],要先找出最大值
        if(f[i]>maxv)maxv=f[i],idx=i;

    int res=0;
    for(int i=0;i<=m;i++)//寻找全部最优选法
        if(f[i]==maxv)res=(res+g[i])%mod;

    cout<<res;//最后输出所有方案
}

第二种:

//这种做法f[i][j]的所有选法总体积不超过j

#include<bits/stdc++.h>
using namespace std;

const int N = 1010,mod=1e9+7;
int f[N];//f[i][j]:从前i个物品中选,总体积不超过j的所有选法
int g[N];//g[i][j]:从前i个物品中选,总体积不超过j的最优方案数量
int n,m;

int main()
{
    cin>>n>>m;

    for(int i=0;i<=m;i++)//从前0个物品中选的最优方案自然都是0,所以g[0~m]都有一种最优方案
        g[i]=1;

    for(int i=1;i<=n;i++)//循环内的程序都是一模一样的,目的就是求出g[m]
    {
        int v,w;
        cin>>v>>w;

        for(int j=m;j>=v;j--)
        {
            int maxv,s=0;
            maxv=max(f[j],f[j-v]+w);

            if(maxv==f[j])s+=g[j]%mod;
            if(maxv==f[j-v]+w)s=(s+g[j-v])%mod;

            f[j]=maxv,g[j]=s;
        }
    }

    cout<<g[m];//因为其表示是总体积不超过j,所以g[m]一定存储着最大值
}

收工!