#include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; struct S { int w, c; } s[100]; int main(void) { int w, n; cin >> w >> n; int dp[w + 1] = {0}; for (int i = 0; i < n; i++) cin >> s[i].w >> s[i].c; for (int i = 0; i < n;i++){ for (int j = w; j >= s[i].w;j--){ dp[j] = max(dp[j], dp[j - s[i].w] + s[i].c); } } cout << dp[w] << endl; } |
Double click to view unformatted code.