Table of contents

• Problem
• Computetional complexity
• Solution

# Problem

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

# Computetional complexity

$O(NW)$

where N is the number of items and W is the capacity

# 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 V_MAX 1000
#define W_MAX 1000
#define N_MAX 100
#define CAP_MAX 10000
#define W_INF 1001

struct Item { Int value, weight; };

Int N, CAP;
vector<Item> items;
Int dp[CAP_MAX+1][N_MAX+1];


Int solve() {
  loop(n,0,N+1) {
    dp[0][n] = 0;
  }

  loop(cap,0,CAP+1) {
    dp[cap][0] = 0;
  }

  loop(n,1,N+1) {
    Item item = items[n];
    loop(cap,1,CAP+1) {
      if (item.weight > cap) continue;
      dp[cap][n] = max(dp[cap][n-1], dp[cap-item.weight][n-1] + item.value);
    }
  }
  return dp[CAP][N];
}


int main(void) {
  Int v, w;
  cin >> N >> CAP;
  items.push_back({0, W_INF}); // dummy
  while (cin >> v >> w) {
    items.push_back({ v, w });
  }

  cout << solve() << endl;
  return 0;
}