C++ 代码

define INF 0x3f3f3f3f

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
int n,W;
int w[1001],v[1001];
int dp[1001][1001],cnt[1001][1001];
//这道题标准状态数组，一个用来存最优方案，一个用来存个数
const int mod =1e9+7;
int main()
{
cin>>n>>W;
for(int i=1;i<=n;i)
{
cin>>w[i]>>v[i];
}
cnt[0][0]=1;
//注意这里一定要给cnt初值
for(int i=1;i<=n;i)
{
for(int j=0;j<=W;j)
{
if(j >= w[i])//当放得下的时候
{
if(dp[i-1][j] < dp[i-1][j-w[i]] + v[i])//当放这个东西的收益比不放的时候大的识货
{
dp[i][j]=dp[i-1][j-w[i]] + v[i];
cnt[i][j]=cnt[i-1][j-w[i]];
//其实这里可以这样看，因为要放这个东西，假设原来已经放了n个东西
//则原来的方案个数为n，现在的方案个数为n*1=n，所以个数其实就是不放这个东西时的数量
}
else if(dp[i-1][j] == dp[i-1][j-w[i]] + v[i])
//当两种办法都可以选的时候
{
dp[i][j]=dp[i-1][j];//或者dp[i-1][j-w[i]] + v[i]，因为值都一样，随便选一个都行
//因为这里是两种办法都可以，所以其实方案的个数就是选或不选的方案个数的和1
cnt[i][j]= (cnt[i-1][j] + cnt[i-1][j-w[i]]) % mod;
}
else
{
dp[i][j]=dp[i-1][j];
cnt[i][j]=cnt[i-1][j];
}
}
else
{
dp[i][j]=dp[i-1][j];
cnt[i][j]=cnt[i-1][j];
}
}
}
int ans=0;
int maxn=-INF;
for(int i=0;i<=W;i)
{
if(maxn < dp[n][i])
maxn=dp[n][i];
}
//因为这里dp的最大的值肯定在最后一排，因为即使不会加，但是也不会减少
//所以dp的最大值一定在最后一排
for(int i=0;i<=W;i++)
{
if(dp[n][i] == maxn)
ans=(ans+cnt[n][i]) % mod;
}

cout<<ans;
return 0;

}
/
4 5
1 2
2 4
3 4
4 6
/