AcWing 11 背包问题求方案数

 代码写的字数比较多, 但是感觉还挺好理解的

#include <bits/stdc++.h>
#define int long long#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int N = 1005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;int n, m, k, x, y, z, ans, t;
int v[N], w[N], f[N][N], f2[N][N];void solve()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ){cin >> v[i] >> w[i];}for (int i = 0; i <= m; i ++ ){f2[0][i] = 1;}for (int i = 1; i <= n; i ++ ){for (int j = m; j >= 0; j -- ){f[i][j] = f[i - 1][j];f2[i][j] = f2[i - 1][j];if (j < v[i]) continue;if (f[i][j] == f[i - 1][j - v[i]] + w[i]){f[i][j] = f[i - 1][j];f2[i][j] = (f2[i][j] + f2[i - 1][j - v[i]]) % mod;}else if (f[i][j] < f[i - 1][j - v[i]] + w[i]){f[i][j] = f[i - 1][j - v[i]] + w[i];f2[i][j] = f2[i - 1][j - v[i]];}else{f[i][j] = f[i - 1][j];f2[i][j] = f2[i - 1][j];}}}cout << f2[n][m] << endl;
}signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;
//	cin >> T;while (T -- ){solve();}
}