Table of contents

• Problem
• Time complexity
• Solution

# Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C

# Time complexity

$O(N CAP)$

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_N 101
#define MAX_V 1001
#define MAX_CAP 10001

struct Item { Int value, weight; };

Int N, CAP;
vector<Item> items(MAX_N, {-1, -1});
vector<Int> dp(MAX_CAP, 0);
Int v, w;

void input() {
  cin >> N >> CAP;
  loop(n,0,N) {
    cin >> v >> w;
    items[n] = { v, w };
  }
}

void solve() {
  loop(cap,1,CAP+1) {
    loop(n,0,N) {
      if (items[n].weight <= cap)
        dp[cap] = max(dp[cap-items[n].weight] + items[n].value, dp[cap]);
    }
  }
  cout << dp[CAP] << endl;
}

int main(void) {
  input();
  solve();
}