acwing11. 背包问题求方案数

题目

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

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

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

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

题解

f[j]表示体积恰好为j时最大价值，g[i]表示体积恰好为j时的方案数。
在选择第i件物品时，可以选也可以不选，此时需要看两者的最大价值（f[j]的意义是体积恰好为j的最大价值）
如果不选的价值最大，那么方案数cnt只需要g[j-1]种，如果选的话，那么方案数就是g[j-v]，如果两者一样大，cnt=（g[j-1]+g[j-v]）

#include<iostream>
#include<cstring>
using namespace std;
const int N=1010,mod=1e9+7;
int n,m;

int f[N],g[N];


int main(){
    cin>>n>>m;
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    g[0]=1;
    for(int i=0;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 cnt=0;
            if(f[j]==maxv)cnt+=g[j];
            if(maxv==f[j-v]+w)cnt+=g[j-v];
            f[j]=maxv,g[j]=cnt%mod;
        }
    }
    int res=0;
    for(int i=0;i<=m;i++)res=max(res,f[i]);//找到最大价值w
    int cnt=0;
    for(int i=0;i<=m;i++){
        if(res==f[i]){//找到等于最大价值的方案
            cnt =(cnt+g[i])%mod;//累加所有等于最大价值的方案数
        }
    }
    cout<<cnt<<endl;
    return 0;
}