鄙人不才，此中鄙陋甚多，望海涵！

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示 方案数 模 109+7 的结果。

数据范围
0<N,V≤1000
0<vi,wi≤1000

样例

输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
2

算法1

f[i][j]表示从前i个物品中选择，体积就是j的价值，g[i][j]表示表示从前i个物品种选择

体积就是j的最大价值对应方案数

从这个状态表示我们就该想到它与普通01背包的区别了，我们需要在开始将所有的f都初始化为负无穷，那么不能使体积恰好为j的情况就会被淘汰（指不会被递推过去）

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1010,mod=1e9+7;

int f[N],g[N];

int main()
{
    int n,m;
    cin>>n>>m;
    memset(f,-0x3f,sizeof f);
    f[0]=0,g[0]=1;//显然选体积为0价值为0，而什么都不选的选法为1
    int mt=0;//用于保存最大值
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            int maxv=max(f[j],f[j-v]+w);
            int s=0;//s这个临时变量存储的是能递推过来的最大价值的方案数
            if(maxv==f[j]) s+=g[j];//当maxv==f[j]时，说明最大价值可由上一层递推过来
            //那么s就需要加上上一层的方案数
            if(maxv==f[j-v]+w)  s=(s+g[j-v])%mod;//当maxv==f[j-v]+w时，说明最大价值可由本层递推过来
            //那么s就需要加上本层的方案数
            f[j]=maxv,g[j]=s;//最终体积为j的对应的最大价值的方案数便为s
            mt=max(mt,maxv);
        }
    }

    int res=0;
    for(int i=1;i<=m;i++)//mt就是最大价值
        if(f[i]==mt)  res=(res+g[i])%mod;
    cout<< max(res, 1) <<endl;
    return 0;
}

算法2

f[i][j]表示从前i个物品中选择，体积不超过j的价值，g[i][j]表示从前i个物品中选择

体积不超过j的最大价值对应方案数

从这个状态表示我们可以看出这是一种与01背包相似的亲民的写法

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010,mod=1e9+7;

int f[N],g[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=m;i++) g[i]=1;//初始化时我们易知，不论是哪个体积下，总有一个对应的最大价值，方案数为1

    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            if(f[j]<f[j-v]+w)
            {
                g[j]=g[j-v]; //当f[j]<f[j-v]+w时，说明g[j]只能从上层转移过来了
                f[j]=f[j-v]+w;
            }
            else if(f[j]==f[j-v]+w) g[j]=(g[j]+g[j-v])%mod;//若相等，说明存在了2个节点，他们路径都符合条件
            //可以递推到g[j]
        }
    }

    cout<< g[m] <<endl;//最后输出这个体积不超过m对应最大价值的方案数即可！
    return 0;
}