题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int f[1010],g[1010];
int main()
{   int n,m;
    cin>>n>>m;
    g[0]=1;
    int mod=1000000007;
    for(int i=1;i<=m;i++) f[i]=-1000000;
    for(int i=1;i<=n;i++)
    {   int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            int t=max(f[j],f[j-v]+w);
            int s=0;
            if(t==f[j]) s=s+g[j]; //加上体积为j的时候的方案数
            if(t==f[j-v]+w) s=s+g[j-v]; //加上体积为j-v的时候的方案数
            if(s>mod) s=s-mod;
            g[j]=s; //更新方案数
            f[j]=t; //更新体积的最大价值
        }
    }
    int maxt=0,res=0;
    for(int i=0;i<=m;i++) maxt=max(maxt,f[i]); //找到最优解
    for(int i=0;i<=m;i++)
    {
        if(f[i]==maxt)
            res+=g[i]; //最优解累加
        res%=mod;
    }
    cout<<res;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla