AcWing 11. 背包问题求方案数
原题链接
中等
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = -1e8, mod = 1e9 + 7;
int n, m;
int dp[N], g[N];
int main() {
cin >> n >> m;
// 不能用memset
for (int i = 1; i <= n; i++) dp[i] = INF;
g[0] = 1;
for (int i = 1; i <= n; i++) {
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j--) {
int a = max(dp[j], dp[j - v] + w), b = 0;
// 此处不能用if-else,因为有可能既能从子问题A,也能从B转化来
if (a == dp[j]) b += g[j];
if (a == dp[j - v] + w) b += g[j - v];
g[j] = b % mod;
dp[j] = a;
}
}
int maxW = 0, ans = 0;
for (int i = 0; i <= m; i++) maxW = max(maxW, dp[i]);
for (int i = 0; i <= m; i++)
if (dp[i] == maxW) {
ans = (ans + g[i]) % mod;
}
cout << ans;
return 0;
}