AcWing 11. 背包问题求方案数
原题链接
中等
作者:
总有刁民想害朕
,
2020-03-13 13:22:07
,
所有人可见
,
阅读 718
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int dp[N];//表示背包中已经放入的物品的总体积为 j 时的最大价值
int cnt[N];//表示背包中已经放入的物品的总体积为 j 时的最大价值 的 放法
int n, m;
int main(){
cin >> n >> m;
memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
cnt[0] = 1;
for(int i = 0;i < n;++i){
int v, w;
cin >> v >> w;
for(int j = m;j >= v;--j){
int maxv = -1, k = 0;
maxv = max(dp[j], dp[j-v]+w);
if(dp[j] == maxv) k = (k + cnt[j]) % mod;
if((dp[j-v]+w) == maxv) k = (k + cnt[j-v])%mod;
cnt[j] = k;
dp[j] = maxv;
}
}
int maxp = -1;
for(int j = 0;j <= m;++j)
if(dp[j] > maxp)
maxp = dp[j];
int sum = 0;
for(int j = 0;j <= m;++j)
if(dp[j] == maxp){
sum = (sum + cnt[j]) % mod;
}
cout << sum << endl;
}