#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 10; int w[N], v[N]; long long f[2][100010]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (j >= w[i]) f[i%2][j] = max(f[(i - 1)%2][j], v[i] + f[(i - 1)%2][j - w[i]]); else f[i%2][j] = f[(i - 1)%2][j]; } } cout << f[n%2][m]; return 0; }
共 2 条回复
#include <bits/stdc++.h> #define endl "\n" using namespace std; int const N = 1000 + 10; int const M = 100000 + 1; long long const MOD=1e9+7; long long w[N], v[N],c[N]; long long f[N][M]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freeopen(".in","r",stdin); //freeopen(".out","w",stdout); int n, m, t = 0, x, y, z; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> w[i] >> c[i]; } f[0][0]=1; for(int i=1;i<=n;i++){ f[i][0]=1; for(int j=1;j<=m;j++){ for(int k=0;k<=c[i]&&j-kw[i]>=0;k++){ f[i][j]+=f[i-1][j-kw[i]]; f[i][j]%=MOD; } } } cout<<f[n][m]; return 0; }
#include <bits/stdc++.h> #define endl "\n" using namespace std; int const N = 1000 + 10; int const M = 100000 + 1; long long const MOD=1e9+7; long long w[N], v[N],c[N]; long long f[N][M]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freeopen(".in","r",stdin); //freeopen(".out","w",stdout); int n, m, t = 0, x, y, z; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> w[i] >> c[i]; } f[0][0]=1; for(int i=1;i<=n;i++){ f[i][0]=1; for(int j=1;j<=m;j++){ for(int k=0;k<=c[i]&&j-kw[i]>=0;k++){ f[i][j]+=f[i-1][j-kw[i]]; f[i][j]%=MOD; } } } cout<<f[n][m]; return 0; }