組み合わせ最適化パターン別解法

はじめに

AOJの 組み合わせ最適化 コースの問題を解きました．
考え方と実装のまとめ記事になります．
プログラミングコンテストチャレンジブック を参考書として使っています．

Coin Changing Problem

コイン問題
額面が $c_1, c_2, \cdots, c_m$ 円の $m$ 種類のコインを使って $n$ 円を支払うときのコインの最小の枚数を求めよ．
各額面のコインは何度でも使用できるとする．

• $1 \leq n \leq 50000$
• $1 \leq m \leq 20$
• $1 \leq c_i \leq 10000$
• $c_i \neq c_j (i \neq j)$ であり，$c_i = 1$ となる $i$ が必ず存在する

考え方

具体例で考えます．
1, 2, 7, 8, 12, 50円の6種類のコインで15円を支払うこととします．
最小の枚数は，7円コイン1枚と8円コイン1枚の組み合わせの2枚です．
これを動的計画法で解いてみます．
$i$ 番目までのコインを使って $j$ 円を支払うときのコインの最小枚数を $dp_{i,j}$ と置きます．
$j$ 円を支払うのに $i + 1$ 番目のコイン $c_{i + 1}$ を(a)使わない場合と(b)使う場合を考えます．

(a) $i + 1$ 番目のコインを使わない
$i$ 番目までのコインで $j$ 円を支払うときの最小枚数と同じ値になります．

dp_{i + 1, j} = dp_{i, j}

(b) $i + 1$ 番目のコインを使う
$i + 1$ 番目のコイン $c_{i + 1}$ を $k$ 枚使うとします．

dp_{i + 1, j} = {\rm min}(dp_{i, j - k \cdot c_{i + 1}} + k \mid k \geq 0,  k \cdot c_{i + 1} \leq j) \tag{1}

しかし，計算量が ${\rm O}(nm^{2})$ となり不十分なので，以下のように式変形します．

\begin{align}
dp_{i + 1, j} &= {\rm min}(dp_{i, j - k \cdot c_{i + 1}} + k \mid k \geq 0,  k \cdot c_{i + 1} \leq j) \\
&= {\rm min}(dp_{i, j}, {\rm min}(dp_{i, j - k \cdot c_{i + 1}} + k \mid k \geq 1,  k \cdot c_{i + 1} \leq j)) \\
&= {\rm min}(dp_{i, j}, {\rm min}(dp_{i, j - (k + 1) \cdot c_{i + 1}} + (k + 1) \mid (k + 1) \geq 1,  (k + 1) \cdot c_{i + 1} \leq j)) \ \because k \rightarrow k + 1 \\
&= {\rm min}(dp_{i, j}, {\rm min}(dp_{i, (j - c_{i + 1}) - k \cdot c_{i + 1}} + k \mid k \geq 0,  k \cdot c_{i + 1} \leq j - c_{i + 1}) + 1) \\
&= {\rm min}(dp_{i, j}, dp_{i + 1, j - c_{i + 1}} + 1) \ \because (1)
\end{align}

(a), (b)をまとめた漸化式が得られます．

\begin{align}
dp_{i + 1, j} &= \begin{cases}
    {\rm min}(dp_{i, j}, dp_{i + 1, j - c_{i + 1}} + 1) & {\rm if} \ j \geq c_{i + 1} \\
    dp_{i, j} & {\rm otherwise}
\end{cases}
\end{align}

また，0番目までのコインを使う，つまりコインを使わないで $j$ 円を支払う場合，
$j = 0$ であれば最小枚数は0枚，$j > 0$ であれば支払えないので $\infty$ となります．

\begin{align}
dp_{0, j} &= \begin{cases}
    0 & {\rm if} \ j = 0 \\
    \infty & {\rm otherwise}
\end{cases}
\end{align}

では，表を使って値の更新を追います．

$i \backslash j$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
2	0	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8
3	0	1	1	2	2	3	3	1	2	2	3	3	4	4	2	3
4	0	1	1	2	2	3	3	1	1	2	2	3	3	4	2	2
5	0	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2
6	0	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2

2番目までの1, 2円コインで3円を支払うときの最小の枚数 $dp_{2, 3}$ は，
$min(dp_{1, 3}, dp_{2, 1} + 1) = min(3, 1 + 1) = 2$ で計算されます．
最終的に計算された $dp_{6, 15}$ が答えになります．

実装

初期値と漸化式が分かっていれば，そのまま実装するだけです．計算量は ${\rm O}(nm)$ です．
額面の最小値は1であり，支払額の最大値は50000なので，最小枚数は50000以下になります．
よって，INFは50000を超えていれば問題ありません．
また，配列の添字は0始まりなので，プログラムの漸化式は $c_i$ となっています．
memsetはバイト単位で初期化するので，fillを使って初期化しています．

#include <iostream>
using namespace std;
int main() {
    const int MAX_N = 50000, MAX_M = 20, INF = 50001;
    int n, m, c[MAX_M];
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
    }
    int dp[MAX_M + 1][MAX_N + 1];
    fill(dp[0], dp[0] + n + 1, INF);
    dp[0][0] = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (j >= c[i]) {
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - c[i]] + 1);
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

0-1 Knapsack Problem

0-1 ナップザック問題
価値と重さがそれぞれ $v_i, w_i$ の $N$ 個の品物と，容量が $W$ のナップザックがある．
重さの総和が $W$ を超えないよう品物を選んだときの価値の総和の最大値を求めよ．

• $1 \leq N \leq 100$
• $1 \leq v_i \leq 1000$
• $1 \leq w_i \leq 1000$
• $1 \leq W \leq 10000$

考え方

コイン問題が分かっていれば，難しくありません．
$i$ 番目までの品物から重さの総和が $j$ 以下となるように選んだときの価値の総和の最大値を $dp_{i, j}$ と置きます．
$i + 1$ 番目の品物を(a)選ばない場合と(b)選ぶ場合を考えます．

(a) $i + 1$ 番目の品物を選ばない
$i$ 番目までの品物から選んだ重さの総和の最大値と同じ値になります．

dp_{i + 1, j} = dp_{i, j}

(b) $i + 1$ 番目の品物を選ぶ
$dp_{i, j - w_{i + 1}}$ に重さ $w_{i + 1}$ で価値 $v_{i + 1}$ の品物を加えます．

dp_{i + 1, j} = dp_{i, j - w_{i + 1}} + v_{i + 1}

(a), (b)をまとめて漸化式が得られます．

\begin{align}
dp_{i + 1, j} &= \begin{cases}
    {\rm max}(dp_{i, j}, dp_{i, j - w_{i + 1}} + v_{i + 1})  & {\rm if} \ j \geq w_{i + 1} \\
    dp_{i, j} & {\rm otherwise}
\end{cases}
\end{align}

0番目までの品物を選ぶ，つまり何も選ばない場合，価値の総和の最大値は0になります．

dp_{0, j} = 0

実装

計算量は ${\rm O}(NW)$ です．
配列の添字は0始まりなので，プログラムの漸化式では $v_i, w_i$ になっています．

#include <cstring>
#include <iostream>
using namespace std;
int main() {
    const int MAX_N = 100, MAX_W = 10000;
    int N, W, v[MAX_N], w[MAX_N];
    cin >> N >> W;
    for (int i = 0; i < N; ++i) {
        cin >> v[i] >> w[i];
    }
    int dp[MAX_N + 1][MAX_W + 1];
    memset(dp[0], 0, sizeof(dp[0]));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= W; ++j) {
            if (j >= w[i]) {
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
    cout << dp[N][W] << endl;
    return 0;
}

Knapsack Problem

ナップザック問題
価値と重さがそれぞれ $v_i, w_i$ の $N$ 個の品物と，容量が $W$ のナップザックがある．
重さの総和が $W$ を超えないよう品物を選んだときの価値の総和の最大値を求めよ．
ただし，同じ品物はいくつでも選ぶことができるとする．

• $1 \leq N \leq 100$
• $1 \leq v_i \leq 1000$
• $1 \leq w_i \leq 1000$
• $1 \leq W \leq 10000$

考え方

0-1 ナップザック問題に「同じ品物はいくつでも選ぶことができる」という条件が追加されています．
これはコイン問題の考え方で解けます．
$i$ 番目までの品物から重さの総和が $j$ 以下となるように選んだときの価値の総和の最大値を $dp_{i, j}$ と置きます．
$i + 1$ 番目の品物を(a)選ばない場合と(b)選ぶ場合を考えます．

(a) $i + 1$ 番目の品物を選ばない
$i$ 番目までの品物から選んだ重さの総和の最大値と同じ値になります．

dp_{i + 1, j} = dp_{i, j}

(b) $i + 1$ 番目の品物を選ぶ
$i + 1$ 番目の品物を $c_{i + 1}$ を $k$ 個選ぶとします．

dp_{i + 1, j} = {\rm max}(dp_{i, j - k \cdot w_{i + 1}} + k \cdot v_{i + 1} \mid k \geq 0,  k \cdot w_{i + 1} \leq j) \tag{2}

コイン問題と同様に式変形します．

\begin{align}
dp_{i + 1, j} &= {\rm max}(dp_{i, j - k \cdot w_{i + 1}} + k \cdot v_{i + 1} \mid k \geq 0, k \cdot w_{i + 1} \leq j) \\
&= {\rm max}(dp_{i, j}, {\rm max}(dp_{i, j - k \cdot w_{i + 1}} + k \cdot v_{i + 1} \mid k \geq 1, k \cdot w_{i + 1} \leq j)) \\
&= {\rm max}(dp_{i, j}, {\rm max}(dp_{i, j - (k + 1) \cdot w_{i + 1}} + (k + 1) \cdot v_{i + 1} \mid (k + 1) \geq 1, (k + 1) \cdot w_{i + 1} \leq j)) \ \because k \rightarrow k + 1 \\
&= {\rm max}(dp_{i, j}, {\rm max}(dp_{i, (j - w_{i + 1}) - k \cdot w_{i + 1}} + k \cdot v_{i + 1} \mid k \geq 0, k \cdot w_{i + 1} \leq j - w_{i + 1}) + v_{i + 1}) \\
&= {\rm max}(dp_{i, j}, dp_{i + 1, j - w_{i + 1}} + v_{i + 1}) \ \because (2) \\
\end{align}

(a), (b)をまとめて漸化式が得られます．

\begin{align}
dp_{i + 1, j} &= \begin{cases}
    {\rm max}(dp_{i, j}, dp_{i + 1, j - w_{i + 1}} + v_{i + 1})  & {\rm if} \ j \geq w_{i + 1} \\
    dp_{i, j} & {\rm otherwise}
\end{cases}
\end{align}

0番目までの品物を選ぶ，つまり何も選ばない場合，価値の総和の最大値は0になります．

dp_{0, j} = 0

実装

0-1 ナップザック問題を解いたプログラムの漸化式を変更するだけです．
計算量は ${\rm O}(NW)$ です．

#include <cstring>
#include <iostream>
using namespace std;
int main() {
    const int MAX_N = 100, MAX_W = 10000;
    int N, W, v[MAX_N], w[MAX_N];
    cin >> N >> W;
    for (int i = 0; i < N; ++i) {
        cin >> v[i] >> w[i];
    }
    int dp[MAX_N + 1][MAX_W + 1];
    memset(dp[0], 0, sizeof(dp[0]));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= W; ++j) {
            if (j >= w[i]) {
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
    cout << dp[N][W] << endl;
    return 0;
}

Longest Increasing Subsequence

最長増加部分列
数列 $A = a_0, a_1, \cdots, a_{n − 1}$ の増加部分列のうち，最長のものの長さを求めよ．
増加部分列とは，すべての $i < j$ で $a_i < a_j$ を満たす部分列のことを言う．

• $1 \leq n \leq 100000$
• $0 \leq a_i \leq 10^9$

考え方

長さが $i + 1$ であるような増加部分列の最終要素の最小値を $dp_i$ と置きます．
そのような増加部分列が存在しない場合は $\infty$ とします．
数列を先頭から順に見ていき，各 $a_j$ について $dp_{i} < a_j$ ならば $dp_{i + 1} = min(dp_{i + 1}, a_j)$ で更新します．
最終的に $dp_i < \infty$ となるような最大の $i$ が答えになります．
では，$A = {4, 2, 1, 6, 3, 5}$ を例に表で追います．

$i$	0	1	2	3	4	5	6
初期	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
$a_0$	4	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
$a_1$	2	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
$a_2$	1	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
$a_3$	1	6	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
$a_4$	1	3	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
$a_5$	1	3	5	$\infty$	$\infty$	$\infty$	$\infty$

実装

各 $a_j$ について $i$ を $0$ から順に $n$ まで動かし，$dp_i$ と比較すると，計算量は ${\rm O}(n^2)$ となります．
$dp$ の配列は単調増加であるため，$dp_i < a_j < dp_{i + 1}$ となる $j$ を二分探索で求めることができます．
この探索にlower_boundを使っています．これで計算量を ${\rm O}(n \log n)$ にできます．
$a_j \geq$ INF となる最小の $a_j$ のポインタ lower_bound(dp, dp + n, INF) と先頭のポインタ dp の差で
最長増加部分列の長さを求めています．
また，$a_i$ の最大値は $10^9$ なので，INFは $10^9$ を超えていれば問題ありません．

#include <iostream>
using namespace std;
int main() {
    const int MAX_N = 100000, INF = 1000000001;
    int n, a;
    cin >> n;
    int dp[MAX_N];
    fill(dp, dp + n, INF);
    for (int i = 0; i < n; ++i) {
        cin >> a;
        *lower_bound(dp, dp + n, a) = a;
    }
    cout << lower_bound(dp, dp + n, INF) - dp << endl;
    return 0;
}

Edit Distance

編集距離
２つの文字列 $s_1, s_2$ の編集距離（レーベンシュタイン距離）を求めよ．
編集距離とは，以下3種類の操作によって，1つの文字列を別の文字列に変形するのに必要な手順の最小回数のことを言う．
挿入：文字列に1文字を挿入
削除：文字列から1文字を削除
置換：文字列の中の1文字を別の文字に置換

• $1 \leq |s_1| \leq 1000$
• $1 \leq |s_2| \leq 1000$

考え方

$s_1$ の $i$ 番目までの文字列と $s_2$ の $j$ 番目までの文字列の編集距離を $dp_{i, j}$ と置きます．
漸化式は以下になります．

\begin{align}
dp_{i, j} &= {\rm min}(dp_{i - 1, j} + 1, dp_{i, j - 1} + 1, dp_{i - 1, j - 1} + {\rm cost}) \\
{\rm cost} &= \begin{cases}
    0 & {\rm if} \ s_{1_i} = s_{2_j} \\
    1 & {\rm otherwise}
\end{cases}
\end{align}

$i = 0$ のとき，$s_2$ の $j$ 番目までの文字列をそのまま追加すれば良いです．
$j = 0$ のときも同様です．

\begin{align}
dp_{0, j} &= j \\
dp_{i, 0} &= i
\end{align}

実装

初期化と更新をそのまま実装するだけです．
計算量は ${\rm O}(|s_1||s_2|)$ です．

#include <iostream>
using namespace std;
int main() {
    const int MAX_S = 1000;
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    int dp[MAX_S + 1][MAX_S + 1];
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= m; ++j) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int cost = s1[i - 1] == s2[j - 1] ? 0 : 1;
            dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost));
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

0-1 Knapsack Problem II

0-1 ナップザック問題 II
価値と重さがそれぞれ $v_i, w_i$ の $N$ 個の品物と，容量が $W$ のナップザックがある．
重さの総和が $W$ を超えないよう品物を選んだときの価値の総和の最大値を求めよ．

• $1 \leq N \leq 100$
• $1 \leq v_i \leq 100$
• $1 \leq w_i \leq 10000000$
• $1 \leq W \leq 1000000000$

考え方

0-1 ナップザック問題の制約条件が変更され，$W$ が大きくなっています．
$i$ 番目までの品物から重さの総和が $j$ 以下となるように選んだときの価値の総和の最大値を $dp_{i, j}$ と置くと，
計算量は ${\rm O}(NW)$ となり，今回の条件では $W$ が大きいため不十分です．
そこで，$i$ 番目までの品物から価値の総和が $j$ となるように選んだときの重さの総和の最小値を $dp_{i, j}$ と置きます．

\begin{align}
dp_{i + 1, j} &= \begin{cases}
    {\rm min}(dp_{i, j}, dp_{i, j - v_{i + 1}} + w_{i + 1})  & {\rm if} \ j \geq v_{i + 1} \\
    dp_{i, j} & {\rm otherwise}
\end{cases}
\end{align}

0番目までの品物を選ぶ，つまり品物を選ばない場合，
$j = 0$ であれば重さの総和の最小値は0，$j > 0$ であれば選べないので $\infty$ となります．

\begin{align}
dp_{0, j} &= \begin{cases}
    0 & {\rm if} \ j = 0 \\
    \infty & {\rm otherwise}
\end{cases}
\end{align}

$dp_{N, j} \leq W$ となる最大の $j$ が最終的な答えとなります．

実装

計算量は ${\rm O}(N \sum_i v_i)$ です．

#include <iostream>
using namespace std;
int main() {
    const int MAX_N = 100, MAX_V = 100, INF = 1000000001;
    int N, W, v[MAX_N], w[MAX_N], vsum = 0;
    cin >> N >> W;
    for (int i = 0; i < N; ++i) {
        cin >> v[i] >> w[i];
        vsum += v[i];
    }
    int dp[MAX_N + 1][MAX_N * MAX_V + 1];
    fill(dp[0], dp[0] + MAX_N * MAX_V + 1, INF);
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= vsum; ++j) {
            if (j < v[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
            }
        }
    }
    int res = 0;
    for (int j = 0; j <= vsum; ++j) {
        if (dp[N][j] <= W) {
            res = j;
        }
    }
    cout << res << endl;
    return 0;
}

Knapsack Problem with Limitations

個数制限付きナップザック問題
価値と重さがそれぞれ $v_i, w_i$ の $N$ 種類の品物と，容量が $W$ のナップザックがある．
重さの総和が $W$ を超えないよう品物を選んだときの価値の総和の最大値を求めよ．
ただし，$i$ 番目の品物は $m_i$ 個選ぶことができるとする．

• $1 \leq N \leq 100$
• $1 \leq v_i \leq 1000$
• $1 \leq w_i \leq 1000$
• $1 \leq m_i \leq 10000$
• $1 \leq W \leq 10000$

考え方

これまでのナップザック問題と同じように解こうとしてみます．
$i$ 番目までの品物から重さの総和が $j$ 以下となるように選んだときの価値の総和の最大値を $dp_{i, j}$ と置きます．
漸化式は以下のようになります．

dp_{i + 1, j} = {\rm max}(dp_{i, j - k \cdot w_{i + 1}} + k \cdot v_{i + 1} \mid 0 \leq k \leq m_{i + 1}, k \cdot w_{i + 1} \leq j)

計算量は ${\rm O}(NW \sum_i m_i)$ となり，不十分です．
そこで，$m_i = 1 + 2 + \cdots + 2^k + a$ と分解して考えます．
$1, 2, \cdots, 2^k, a$ の組み合わせで，$1$ から $m_i$ のすべての数を作ることができます．
$i$ 種類目の品物について，重さと価値が $x \cdot w_i, x \cdot v_i (x = 1, 2, \cdots, 2^k, a)$ となる品物が1つずつあると考えます．
2の冪でまとめた品物でナップザック問題を解くことで，計算量を ${\rm O}(NW \log \sum_i m_i)$ とすることができます．

実装

$dp$ は1次元配列として定義し，配列を再利用しています．
これによりメモリを節約することができます．

#include <cstring>
#include <iostream>
using namespace std;
int main() {
    const int MAX_N = 100, MAX_W = 10000;
    int N, W, v[MAX_N], w[MAX_N], m[MAX_N];
    cin >> N >> W;
    for (int i = 0; i < N; ++i) {
        cin >> v[i] >> w[i] >> m[i];
    }
    int dp[MAX_W + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < N; ++i) {
        int num = m[i];
        for (int k = 1; num > 0; k <<= 1) {
            int mul = min(k, num);
            for (int j = W; j >= w[i] * mul; --j) {
                dp[j] = max(dp[j], dp[j - w[i] * mul] + v[i] * mul);
            }
            num -= mul;
        }
    }
    cout << dp[W] << endl;
    return 0;
}

Huge Knapsack Problem

巨大ナップザック問題
価値と重さがそれぞれ $v_i, w_i$ の $N$ 個の品物と，容量が $W$ のナップザックがある．
重さの総和が $W$ を超えないよう品物を選んだときの価値の総和の最大値を求めよ．

• $1 \leq N \leq 40$
• $1 \leq v_i \leq 10^{15}$
• $1 \leq w_i \leq 10^{15}$
• $1 \leq W \leq 10^{15}$

考え方

0-1 ナップザック問題の制約条件が変更され，$v_i, w_i, W$ が大きく，$N$ が小さくなっています．
${\rm O}(NW)$ の計算量では不十分なため，$N$ が小さいのを利用して解きます．
品物の選び方は $2^N$ 通りあるので，計算量は最大で $2^{40}$ となってしまいます．
そこで，半分に分割する方法を考えると $2^{20}$ となり，十分計算できます．
前半分から重さと価値の総和が $W1, V1$ となる選び方をします．
同様に，後ろ半分から重さと価値の総和が $W2, V2$ となる選び方をします．
$W1 + W2 \leq W$ を満たす場合の $V1 + V2$ の最大値が答えとなります．

実装

1. 前半分の全ての選択パターンについて，重さと価値の総和のpair $(W1, V1)$ を要素とするvectorを作成
2. 重さの総和に対して価値の総和が小さい，つまり $W1_i \leq W1_j$ かつ $V1_i \geq V1_j$ となる $j$ 番目の要素を除外
3. 後ろ半分の全ての選択パターンについて，$W1 \leq W - W2$ を満たす最大の $W1$ に対応する $V1$ を取得
4. $V1 + V2$ の最大値が答え

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    const int MAX_N = 40;
    const long long INF = 20 * 1000000000000000 + 1;
    int N;
    long long W, v[MAX_N], w[MAX_N];
    vector<pair<long long, long long>> p;  // (weight, value)
    cin >> N >> W;
    for (int i = 0; i < N; ++i) {
        cin >> v[i] >> w[i];
    }
    int N2 = N / 2;
    for (int i = 0; i < 1 << N2; ++i) {
        long long sw = 0, sv = 0;
        for (int j = 0; j < N2; ++j) {
            if (i >> j & 1) {
                sw += w[j];
                sv += v[j];
            }
        }
        p.push_back(make_pair(sw, sv));
    }
    sort(p.begin(), p.end());
    int m = 1;
    for (int i = 1; i < 1 << N2; ++i) {
        if (p[m - 1].second < p[i].second) {
            p[m] = p[i];
            ++m;
        }
    }
    long long res = 0;
    for (int i = 0; i < 1 << (N - N2); ++i) {
        long long sw = 0, sv = 0;
        for (int j = 0; j < N - N2; ++j) {
            if (i >> j & 1) {
                sw += w[N2 + j];
                sv += v[N2 + j];
            }
        }
        if (sw <= W) {
            pair<long long, long long> _p = make_pair(W - sw, INF);
            long long tv = (lower_bound(p.begin(), p.begin() + m, _p) - 1)->second;
            res = max(res, sv + tv);
        }
    }
    cout << res << endl;
    return 0;
}

おわりに

AOJの組み合わせ最適化コースの考え方と実装をまとめました．
個数制限付きナップザック問題 II がまだ解けていないので，解けたら追記します．