0-1ナップサック問題をC++で解く方法：再帰を使った実装と解説

0-1ナップサック問題とは、それぞれに「重み」と「価値」が設定された複数のアイテムが与えられたとき、ナップサックの容量（許容される総重量）を超えない範囲で、アイテムを選んで合計価値を最大化するという古典的な最適化問題です。各アイテムは「入れるか・入れないか」の2択しかないため、「0-1」と呼ばれます。

この記事では、C++を使って0-1ナップサック問題を再帰的に解くプログラムを紹介します。

入力データ

Value = [10, 20, 30, 40, 60, 70]
Weight = [1, 2, 3, 6, 7, 4]
int w = 7

出力結果

knapsack value is: 100

アルゴリズムの流れ

Begin
   入力：重みと価値を持つアイテムの集合
   ナップサックの容量を設定
   アイテム数 = sizeof(values) / sizeof(values[0])
   Knapsack(価値配列 v, 重み配列 w, アイテム数 n, 容量 W)
   If (w < 0)
      Return
   アイテムが残っていない、または容量が0になった場合
      Return 0
   現在のアイテムnをナップサックに入れる場合：
      v[n] を加算し、残りのアイテム(n - 1)に対して
      容量を W - w[n] に減らして再帰呼び出し
   現在のアイテムnを入れない場合：
      残りのアイテム(n - 1)に対してそのまま再帰呼び出し
   「入れる場合」と「入れない場合」のうち大きい方の値を返す
End

サンプルコード

#include <iostream>
#include <climits>
using namespace std;

int knapSack(int v[], int w[], int n, int W) {
    if (W < 0)
        return INT_MIN;
    if (n < 0 || W == 0)
        return 0;
    int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
    int ex = knapSack(v, w, n - 1, W);
    return max(in, ex);
}

int main() {
    int v[] = { 10, 20, 30, 40, 60, 70 };
    int w[] = { 1, 2, 3, 6, 7, 4 };
    int W = 7;
    int n = sizeof(v) / sizeof(v[0]);
    cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
    return 0;
}

実行結果

Knapsack value is 100

コードのポイント

このプログラムは純粋な再帰（全探索）によって各アイテムを「入れる」「入れない」の両パターンで試し、得られる価値の最大値を返します。

• 容量オーバーの処理： アイテムを入れた結果、容量Wが負になった場合は INT_MIN を返すことで、その選択が無効であることを表現しています。
• 終了条件： すべてのアイテムを検討し終えた（n < 0）か、容量が0になった時点で0を返し、再帰を終了します。
• 計算量： 各アイテムについて2通りの選択肢があるため、時間計算量は O(2^n) となります。アイテム数が増えると指数関数的に遅くなるため、実用的には動的計画法（DP）による O(nW) の実装が推奨されます。

今回の例では、容量7のナップサックに対して価値10（重み1）、30（重み3）、60（重み7）…といった組み合わせの中から最適な選択を行い、最大価値 100 が導き出されます。