ナップサック問題

概要

次のような問題を、ナップサック問題という。
ABCのC問題レベル（簡単なもの）～G問題以上レベル（難しいもの）。

N 個の品物がある。
i 番目の品物の重さは w[i]、価値は v[i] である。
重さの合計が W 以下になるように、いくつかの品物を選ぶ。
選んだ品物の価値の合計の最大値を求めよ。

基本の問題では、各品物は高々 $1$ 回しか選べない。（$0/1$ ナップサック）
この場合、各品物について「選ばない」「選ぶ」の $2$ 通りがある。
よって、愚直に全ての選び方を調べると $O(2^N)$ かかる。

特に制限のない一般の $0/1$ ナップサック問題はNP困難である。
すなわち、現実的な時間で解ける厳密解法があるかどうかは未解決問題である。

一方、何か制約がある場合には、それを利用して解ける場合がある。

（※1）重さの設定がなく、価値自体が基準を超えてはいけないという条件。

典型問題例

• Educational DP Contest D - Knapsack 1

- 重さを添字にする基本的な $0/1$ ナップサック問題。

• Educational DP Contest E - Knapsack 2

- 容量が大きく、価値の総和を添字にする問題。

• ABC032 D - ナップサック問題

- 制約に応じて、半分全列挙・重さDP・価値DPを使い分ける問題。

• Typical DP Contest A - コンテスト

- 部分和問題で、作れる合計値の種類数を求める問題。

• ABC286 D - Money in Hand

- 各種類を使える個数に上限がある部分和問題。

コード例

$0/1$ ナップサック問題、$N$ が最大 $20$ くらい（C問題レベル）

$N$ が最大 $20$ くらいであれば、$O(2^N)$ が間に合う。
これはbit全探索の典型問題なので、解説は省略。

$0/1$ ナップサック問題、$N$ が最大 $40$ くらい（F問題レベル）

$N$ が最大 $40$ くらいであれば、$O(2^{N/2})$ が間に合う。
これは半分全列挙の典型問題なので、概略のみ記す。

• 前半の全ての部分集合について、重さと価値を列挙する
• 後半についても同様に列挙する
• 後半の状態を重さ順に並べ、他の候補より価値が小さいのに重い候補を削除する
• 前半の各状態に対し、残り容量以下で価値が最大の後半状態を二分探索する

$0/1$ ナップサック問題、$W$ が小さめ、重さ合計は $W$ ちょうど指定（D問題レベル）

この形で出題されることはあまりないが、理解の順として必要なので掲載。
典型問題集という意味では、$1$ つ下の形の方が主役。
重さの合計が「$W$ 以下」ではなく、「$W$ ちょうど」にしなければいけない場合の問題。

例として、以下を考える。

品物0: 重さ 2, 価値 2
品物1: 重さ 1, 価値 3
品物2: 重さ 3, 価値 4
要求される重さ: 5

これに対し、以下のようにDPテーブルを用意する。

dp[i][j] = 先頭 i 個の品物だけを使い、重さの合計を j ちょうどにしたときの価値の最大値

明らかにわかる初期データとして、荷物なしの場合の値を埋める。
-INF は、全ての品物の価値を足してもまだ負の数になるくらいの、絶対値が大きな負の数。
そうすることで、負の数が入っていれば実現不可能と判定できる。

その後、品物を $1$ つずつ制限範囲に追加して、テーブルを $1$ 段ずつ埋めていく。
$i$ 番目の品物を制限範囲に追加するときは、次の $2$ 通りを比較する。

• $i$ 番目の品物を選ばない。
• $i$ 番目の品物を選ぶ。

したがって、遷移は次のようになる。

$$
dp[i+1][j]
=
\begin{cases}
\max(dp[i][j],\ dp[i][j-w_i]+v_i) & (j\geq w_i) \\
dp[i][j] & (j<w_i)
\end{cases}
$$

これに従ってテーブルを埋めると、以下のようになり、答えは $6$ となる。
重さがちょうど $5$ でなければならないので、重さ $4$ のところにある $7$ は採用できない。

コードは次のようになる。

vector<vector<long long>> dp(N+1,vector<long long>(W+1,-INF));
dp.at(0).at(0) = 0;

for (int i=0; i<N; i++) {
  for (int j=0; j<=W; j++) {
    dp.at(i+1).at(j) = dp.at(i).at(j);
    if (j>=w.at(i)) {
      dp.at(i+1).at(j) = max(dp.at(i+1).at(j),dp.at(i).at(j-w.at(i))+v.at(i));
    }
  }
}

cout << dp.at(N).at(W) << '\n';

状態数は $(N+1)(W+1)$ 個で、各状態を $O(1)$ で更新する。

• 時間計算量：$O(NW)$
• 空間計算量：$O(NW)$

【高度内容】インラインDPで以下のようにすることもできる。

dp[j] = 処理済みの品物だけを使い、重さの合計を j ちょうどにしたときの価値の最大値

vector<long long> dp(W+1,-INF);
dp.at(0) = 0;

for (int i=0; i<N; i++) {
  for (int j=W; j>=w.at(i); j--) {
    dp.at(j) = max(dp.at(j),dp.at(j-w.at(i))+v.at(i));
  }
}

cout << dp.at(W) << '\n';

• 時間計算量：$O(NW)$
• 空間計算量：$O(W)$

容量 $j$ は、必ず大きい方から小さい方へ処理する。
昇順に処理すると、同じ品物を使って更新した値を、その品物の次の更新でも参照してしまう。

空間計算量は大幅に軽量化、時間計算量は定数程度の軽量化。

$0/1$ ナップサック問題、$W$ が小さめ、重さ合計は $W$ 以下指定（D問題レベル）

最も典型的なナップサック問題。
重さ合計が $W$ ちょうどでなく、余裕を残してもよい場合。
この場合、$2$ つの考え方がある。

$1$ つは、上の問題の方法で $W$ ちょうどの表を作り、最下段の最大値を全探索する方法。
初めてのナップサック問題なら、これで十分。

だが、今後の応用のためにはもう $1$ つの方法を習得したい。
それは、「重さ $1$、価値 $0$ のダミー品物を好きなだけ入れてよい」とする方法。
こうすると、重さ合計 $4$ になる解が、ダミー品物を $1$ つ足した形で重さ合計 $5$ のデータにも反映される。
結果として、DPテーブルが以下の意味を持つようになる。

dp[i][j] = 先頭 i 個の品物だけを使い、重さの合計を j 以下にしたときの価値の最大値

そして、DPテーブルの初期化が次のようになる。

遷移は同じ式で、結果は以下のようになり、答えは $7$ になる。

コードは、初期化が変わるだけ。

vector<vector<long long>> dp(N+1,vector<long long>(W+1,0));

for (int i=0; i<N; i++) {
  for (int j=0; j<=W; j++) {
    dp.at(i+1).at(j) = dp.at(i).at(j);
    if (j>=w.at(i)) {
      dp.at(i+1).at(j) = max(dp.at(i+1).at(j),dp.at(i).at(j-w.at(i))+v.at(i));
    }
  }
}

cout << dp.at(N).at(W) << '\n';

状態数は $(N+1)(W+1)$ 個で、各状態を $O(1)$ で更新する。

• 時間計算量：$O(NW)$
• 空間計算量：$O(NW)$

【高度内容】インラインDPの場合のコードは以下。

vector<long long> dp(W+1,0);

for (int i=0; i<N; i++) {
  for (int j=W; j>=w.at(i); j--) {
    dp.at(j) = max(dp.at(j),dp.at(j-w.at(i))+v.at(i));
  }
}

cout << dp.at(W) << '\n';

• 時間計算量：$O(NW)$
• 空間計算量：$O(W)$

容量 $j$ は、必ず大きい方から小さい方へ処理する。
昇順に処理すると、同じ品物を使って更新した値を、その品物の次の更新でも参照してしまう。

空間計算量は大幅に軽量化、時間計算量は定数程度の軽量化。

$0/1$ ナップサック問題、$\sum v[i]$ が小さめ、重さ合計は $W$ 以下指定（D問題レベル）

容量 $W$ が大きすぎると、$O(NW)$ の標準的な解き方は不可能。
しかし、価値の総和 $\sum v[i]$ が小さければ、双対性を利用して解ける。
つまり、「ある重さ以下での価値の最大値」は、「ある価値に必要な重さの最小値」の一覧から求められる。

例として、前と同じ品物を考える。

品物0: 重さ 2, 価値 2
品物1: 重さ 1, 価値 3
品物2: 重さ 3, 価値 4
容量: 5

これに対し、以下のようにDPテーブルを用意する。

dp[i][x] = 先頭 i 個の品物だけを使い、価値の合計を x ちょうどにするために必要な重さの最小値

価値の合計は最大で $2+3+4=9$ なので、$x=0,1,\ldots,9$ の状態を用意する。
明らかにわかる初期データとして、品物なしの場合の値を埋める。
INF は、全ての品物の重さを足しても届かない程度に大きな値とする。

その後、品物を $1$ つずつ制限範囲に追加して、テーブルを $1$ 段ずつ埋めていく。
$i$ 番目の品物を制限範囲に追加するときは、次の $2$ 通りを比較する。

• $i$ 番目の品物を選ばない。
• $i$ 番目の品物を選ぶ。

したがって、遷移は次のようになる。

$$
dp[i+1][x]
=
\begin{cases}
\min(dp[i][x],\ dp[i][x-v_i]+w_i) & (x\geq v_i) \\
dp[i][x] & (x<v_i)
\end{cases}
$$

これに従ってテーブルを埋めると、以下のようになり、答えは $7$ となる。
価値 $7$ は重さ $4$ で作れるが、価値 $8$ は作れず、価値 $9$ には重さ $6$ が必要なので採用できない。

コードは次のようになる。

int sum_v = accumulate(v.begin(),v.end(),0);
vector<vector<long long>> dp(N+1,vector<long long>(sum_v+1,INF));
dp.at(0).at(0) = 0;

for (int i=0; i<N; i++) {
  for (int x=0; x<=sum_v; x++) {
    dp.at(i+1).at(x) = dp.at(i).at(x);
    if (x>=v.at(i)) {
      dp.at(i+1).at(x) = min(dp.at(i+1).at(x),dp.at(i).at(x-v.at(i))+w.at(i));
    }
  }
}

int answer = 0;
for (int x=0; x<=sum_v; x++) {
  if (dp.at(N).at(x)<=W) answer = x;
}
cout << answer << '\n';

状態数は $(N+1)(\sum v[i]+1)$ 個で、各状態を $O(1)$ で更新する。

• 時間計算量：$O\left(N\sum v[i]\right)$
• 空間計算量：$O\left(N\sum v[i]\right)$

価値の総和自体が大きくても、答えが $B$ 未満であると保証されている場合は有効。
具体的には、$0\leq x<B$ の状態だけを持てばよい。
この場合、時間計算量は $O(NB)$、空間計算量も $O(NB)$ となる。

【高度内容】インラインDPで以下のようにすることもできる。

dp[x] = 処理済みの品物だけを使い、価値の合計を x ちょうどにするために必要な重さの最小値

int sum_v = accumulate(v.begin(),v.end(),0);
vector<long long> dp(sum_v+1,INF);
dp.at(0) = 0;

for (int i=0; i<N; i++) {
  for (int x=sum_v; x>=v.at(i); x--) {
    dp.at(x) = min(dp.at(x),dp.at(x-v.at(i))+w.at(i));
  }
}

int answer = 0;
for (int x=0; x<=sum_v; x++) {
  if (dp.at(x)<=W) answer = x;
}
cout << answer << '\n';

• 時間計算量：$O\left(N\sum v[i]\right)$
• 空間計算量：$O\left(\sum v[i]\right)$

価値 $x$ は、必ず大きい方から小さい方へ処理する。
昇順に処理すると、同じ品物を使って更新した値を、その品物の次の更新でも参照してしまう。

空間計算量は大幅に軽量化、時間計算量は定数程度の軽量化。

部分和問題（D問題レベル）

動的計画法のページで紹介したもの。
重さとコストに同じ値を使用するだけなので、解説は省略。

完全ナップサック問題（D問題レベル）

同じ品物を重ねていくつでも選んでもいい場合もある。
これは、完全ナップサック問題と呼ばれる。
この場合、遷移がこうなる。

$$
dp[i+1][j]
=
\begin{cases}
\max(dp[i][j],\ dp[i+1][j-w_i]+v_i) & (j\geq w_i) \\
dp[i][j] & (j<w_i)
\end{cases}
$$

for (int i=0; i<N; i++) {
  for (int j=0; j<=W; j++) {
    dp.at(i+1).at(j) = dp.at(i).at(j);
    if (j>=w.at(i)) {
      dp.at(i+1).at(j) = max(dp.at(i+1).at(j),dp.at(i+1).at(j-w.at(i))+v.at(i));
    }
  }
}

元の形との差は、その品物を選ぶ場合の遷移を dp[i] からではなく dp[i+1] から行う点。
これにより、一度その荷物を選んだデータに同じ荷物を重ねて採用できる遷移となっている。

【高度内容】インラインDPの場合は、以下。

for (int i=0; i<N; i++) {
  for (int j=w.at(i); j<=W; j++) {
    dp.at(j) = max(dp.at(j),dp.at(j-w.at(i))+v.at(i));
  }
}

元の形との差は、$j$ のループを昇順に行っていること。
これにより、一度その荷物を選んだデータに同じ荷物を重ねて採用できる遷移となっている。

個数制限付きナップサック問題（E問題レベル）

$i$ 番目の品物を最大 $c_i$ 個まで選べるという問題もある。
そのまま $0$ 個から $c_i$ 個まで試すと、計算量が大きくなる。

基本的な高速化は、個数を二進法のように分割する方法である。
例えば、同じ品物を $13$ 個まで使える場合。
この場合、その $13$ 個を、$1$ 個入りパック、$2$ 個入りパック、$4$ 個入りパック、$6$ 個入りパックにわける。
すると、パックの組み合わせ次第で $0$ 個から $13$ 個まで任意の個数を選ぶことができる。

これらを選ぶかどうかで、元の品物を $0$ 個から $13$ 個まで使う全ての場合を表せる。
しかも、$-1$ 個になったり $14$ 個以上になったりすることはない。
そのため、これら $4$ つを別個の品物と思って $0/1$ ナップサック問題を解けばよい。

各個数 $c_i$ を $O(\log(c_i+1))$ 個に分解するため、計算量は $O\left(W\sum_{i=1}^{N}\log(c_i+1)\right)$。

分数ナップサック問題（C問題レベル）

品物が液体などで、「品物 $1$ を $1/3$ だけ選ぶ」のように、量が整数に限られない問題もある。
この場合、「価値/重さ」が大きい順に貪欲法で採用するだけでよい。

グループナップサック問題（D問題レベル）

品物がいくつかのグループに分かれていて、各グループから高々 $1$ 個を選ぶ問題もある。

この場合、基本的には $0/1$ ナップサック問題の解き方となる。
ただし、DPテーブルの各段を、品物 $1$ つではなく、品物 $1$ グループ全てを考慮して更新する。

重さ以外の制限がある場合（E問題レベル）

例えば、重さと体積の両方が制限以下、とかであれば、DPの次元を $1$ つ増やせばいいだけ。
重さと個数の制限の場合も同様。

コードは圧倒的に複雑になるが、考え方が複雑になる部分はほぼない。
次元が $1$ つ上がるとテーブルが一気に大きくなるので、計算量などに注意。

何も制限がない場合（G問題以上レベル）

最悪計算量は $O(2^N)$ だが、$v_i/w_i$ が散らばっている場合に大抵解ける方法がある。
詳しくは「分枝限定法」の記事参照。

AHCでの $0/1$ ナップサック問題

$v_i/w_i$ が大きい品物から選ぶ戦略は、最善の解になるとは限らない。
しかし、最善から遠い解になることもほとんどないので、AHCならそれなりに有効。

注意点

オーバーフローに注意

たくさんの値を足すため、オーバーフローしやすい。
long long 型にする必要があるか、さらには long long 型でもあふれる可能性はないか、よく確認する。

到達不能状態を区別する

「容量以下で最大化」だけなら、全て 0 で初期化できる場合が多い。
しかし、合計をちょうど固定する場合や最小値を求める場合は、未到達状態を -INF や INF で区別する。

INF に値を足すとオーバーフローする場合がある。
INF を $2$ 倍してもオーバーフローしない程度にして、足し算後に INF 以上の値は INF に戻すなどする。

関連アルゴリズム

動的計画法

品物数多めのナップサック問題の基本解法。
品物を順に増やしながら、重さや価値ごとの最適値を引き継ぐ。

bit全探索

$N$ が最大 $20$ くらいの場合は、全ての選び方を直接調べられる。
重さや価値の上限が大きくても使える。

半分全列挙

$N$ が最大 $40$ くらいの場合は、品物を $2$ つのグループに分けて考える。
支配される状態の削除や二分探索と組み合わせる。

分枝限定法

暫定解と上界を用いて、最適解を更新できない探索範囲を打ち切る厳密解法。
一般の $0/1$ ナップサック問題に利用できる場合がある。

バックトレース

最大値だけでなく、実際に選んだ品物を出力する場合に使う。
DP表の遷移を答えの状態から逆向きにたどる。

貪欲法

品物を分割できる分数ナップサック問題では、価値密度順の貪欲法を使う。
一方、$0/1$ ナップサック問題では一般に使えない。

貪欲法（AHC）

品物を分割できないナップサック問題でも、AHCなら価値密度順の貪欲法は有効。