# 目次

• 目次
• 問題
  • 入力
  • 出力
  • 入出力例
• 解説
• 計算量
• 回答1
• 回答2（解答)

# 問題

https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B

それぞれ重さと価値をもった$N$個のアイテムと$W$という容量が与えられます.
容量$W$を超えない範囲でうまくアイテムを選択した場合の価値の最大値を答える問題です.

# 入力

N W
v_1 w_1
v_2 w_2
...
v_N w_N

• N - アイテムの数
• W - 容量
• v_i w_i - $i$番目のアイテムの価値と重さ

# 出力

アイテムをうまく選んだ際の価値の最大値を出力してください.

# 入出力例

4 5
4 2
5 2
2 1
8 3

13

容量が$5$なので、それを超えない範囲でアイテム$5 2$と$8 3$を選ぶと価値は最大値$5 + 8 = 13$となります.

# 解説

各アイテムは選ぶかいなかの2択しかありません.
0-1ナップサック問題と呼ばれる典型問題です.

各アイテムを先頭から、選んだ場合と選ばなかった場合で価値が大きい方を選択していけば答えは出ます.
上の例の場合には以下のような木になります.
左に進むと選んだ場合、右に進むと選ばなかった場合の価値,重さです.
末端の葉の16通りの中で重さが5以下で価値が最大のものが答えです.

                                               0,0
                                    /                       \
                        4,2                                          0,0
                    /           \                                /          \
             9,4                   4,2                    5,2                   0,0
          /       \              /      \               /     \                /     \
     11,5          9,4       6,3         4,2        7,3        5,2        2,1         0,0
     /  \          /  \      /  \        /  \       /  \       /  \       /  \       /  \
  19,8  11,5   17,7  9,4  14,6  6,3   12,5  4,2  15,6  7,3  13,5  5,2   10,4  2,1  8,3   0,0
                                                            ----

このようにアイテムを１つチェックするごとに場合分けが2通り発生しますので、計算量は$O(2^N)$となります.
$N$が20以下の場合には時間内に解けますが、今回は$N$が$100$と大きいので間に合いません.
参考用のためこの場合のソースコードは回答1にあります.

このような問題は動的計画法で効率よく解くことが出来ます.
まずは容量が0と仮定すると、どのアイテムも選択出来ないので最大価値は当然0となります.
容量が1の時には、重さが1以下のものを選択する場合はそのアイテムの価値がそのまま最大価値となります.
容量がcap+1の時には、容量は多ければ多いほどアイテムを積められる可能性は高まるので価値は最低でも容量capの場合の最大値となります.
さらに、今回の容量で始めて解禁される組み合わせもあるはずなので今回のアイテムの重さ分を容量から引いた容量の時の最大価値+今回のアイテムの最大価値が最大値である可能性もあります.
これら２つの大きいほうがcap+1の場合の最大価値になります.
最終的に容量W、アイテムNまで考慮した時の最大価値が答えになります.

動的計画法のテーブルは以下のようになります.

# 計算量

$O(NW)$

# 回答1

TLE（時間制限超過）

$O(2^N)$

// 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;

struct Item {
  Int w, v;
  Item(): w(0),v(0) {}
  Item(Int w, Int v): w(w), v(v) {}
};
istream & operator >> (istream & in, Item & item) {
  Int v, w;
  in >> v; in >> w; item.v = v; item.w = w;
  return in;
}

#define MAX_N 100
#define MAX_W 10000
Int N, W;
vector<Item> items;

void input() {
  cin >> N >> W;
  Item a_;
  while (cin >> a_) items.push_back(a_);
}

Int dfs(Int n, Int value, Int weight) {
  if (n >= N || weight >= W) return value;
  Int max_ = dfs(n + 1, value, weight);
  if (weight + items[n].w <= W)
    max_ = max(max_, dfs(n + 1, value + items[n].v, weight + items[n].w));
  return max_;
}

void solve() {
  cout << dfs(0, 0, 0) << endl;
}

int main() {
  input();
  solve();
  return 0;
}

# 回答2（解答)

struct Item {
  Int w, v;
  Item(): w(0),v(0) {}
  Item(Int w, Int v): w(w), v(v) {}
};
istream & operator >> (istream & in, Item & item) {
  Int v, w;
  in >> v; in >> w; item.v = v; item.w = w;
  return in;
}

#define MAX_N 100
#define MAX_W 10000
Int N, W;
vector<Item> items;
vector<vector<Int> > DP(MAX_N + 1, vector<Int>(MAX_W + 1, 0));

void input() {
  cin >> N >> W;
  Item a_;
  items.push_back(a_);
  while (cin >> a_) items.push_back(a_);
}

Int dp() {
  loop(n,1,N+1) {
    Item item = items[n];
    loop(cap,1,W+1) {
      DP[n][cap] = DP[n-1][cap];
      if (cap >= item.w)
        DP[n][cap] = max(DP[n][cap], DP[n-1][cap-item.w] + item.v);
    }
  }
  return DP[N][W];
}

void solve() {
  cout << dp() << endl;
}

int main() {
  input();
  solve();
  return 0;
}