#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <vector> using namespace std; struct S{ int weight; int value; }s[1001]; int main(void) { int max_weight, n; scanf("%d %d",&max_weight,&n); for (int i = 0; i < n;i++){ scanf("%d %d", &s[i].weight, &s[i].value); } int dp[max_weight + 1] = {0}; for (int i = 0; i < n;i++){ for (int j = max_weight; j >= s[i].weight;j--){ dp[j] = max(dp[j], dp[j - s[i].weight] + s[i].value); } } cout << dp[max_weight] << endl; } |
Double click to view unformatted code.