knapsack - iterativna dinamika, jos manje memorije

#include <cstdio>
#include <algorithm>
#include <cstring>

const int MAXN = 2010;

int s, n;
int dp[MAXN];
int a[MAXN];
int b[MAXN];

int main() {
  scanf("%d%d", &s, &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &a[i], &b[i]);
  }

  for (int i = 0; i < n; ++i) {
    for (int j = s; j >= 0; --j) {
      if (j + a[i] <= s) {
        dp[j + a[i]] = std::max(dp[j + a[i]], dp[j] + b[i]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i <= s; ++i) {
    ans = std::max(ans, dp[i]);
  }
  printf("%d\n", ans);
  return 0;
}