C++ 代码
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<limits.h>
using namespace std;
const int mid=1e9+7;
const int N=1010;
int f[N];//表示放入i件物品的最大价值
int c[N];//表示放入i件物品的最大方案数
int n,m;
int main()
{
cin>>n>>m;
for(int i=0;i<=n;i++)
{
c[i]=1;//即使放入物品的话,其方案数也算一种
}
for(int i=1;i<=n;i++)
{
int v,w;
cin>>v>>w;
for(int j=m;j>=v;j--)
{
if(f[j-v]+w>f[j])
{
f[j]=f[j-v]+w;//如果我们加入v后的价值大于原有的价值,我们就重新更新
c[j]=c[j-v];//这个时候的方案数不变
}
else if(f[j-v]+w==f[j])
{
c[j]=(c[j]+c[j-v])%mid;
}
}
}
cout<<f[m]<<endl;
return 0;
}