C++で動的計画法により0-1ナップサック問題を解く方法：アルゴリズムと実装例

本記事では、動的計画法（Dynamic Programming）を用いて0-1ナップサック問題を解くC++プログラムを紹介します。0-1ナップサック問題とは、それぞれ重さと価値が異なる複数の品物が与えられたとき、ナップサックの容量（許容重量）を超えない範囲で、合計価値が最大になるように品物を選ぶ組合せ最適化問題です。「0-1」という名称は、各品物について「選ぶ（1）」か「選ばない（0）」の二択しかないことに由来しています。

動的計画法によるアプローチ

すべての品物の組み合わせを総当たりで調べる全探索では、品物の数に対して計算量が指数関数的に増大してしまいます。そこで有効なのが動的計画法です。部分問題の答えを表（テーブル）に記録しながら処理を進めることで、効率的に最適解を求められます。

ここでは、K[i][wt] を「最初の i 個の品物の中から、容量 wt 以内で選んだときの最大価値」と定義します。この表を順に埋めていき、最終的な K[n][W] が求める答えとなります。

漸化式（再帰関係）

• i == 0 または wt == 0 のとき： K[i][wt] = 0（品物がない、または容量がないため価値は0）
• w[i-1] <= wt のとき（i番目の品物が入る場合）： K[i][wt] = max(v[i-1] + K[i-1][wt - w[i-1]], K[i-1][wt])（その品物を入れる場合と入れない場合の大きい方を採用）
• それ以外の場合： K[i][wt] = K[i-1][wt]（その品物は入れない）

アルゴリズム

開始
　各品物の重み w[] と価値 v[] を入力する
　ナップサックの容量 W を設定する
　2つの整数のうち大きい方を返す関数 max(x, y) を用意する
　最大価値を返す関数 knapSack(W, w[], v[], n) を作成する
　　int i, wt;
　　int K[n + 1][W + 1]
　　for i = 0 to n
　　　for wt = 0 to W
　　　　if (i == 0 or wt == 0)
　　　　　K[i][wt] = 0
　　　　else if (w[i - 1] <= wt)
　　　　　K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt])
　　　　else
　　　　　K[i][wt] = K[i - 1][wt]
　　return K[n][W]
　関数を呼び出し、結果を出力する
終了

サンプルコード

#include <iostream>
using namespace std;

int max(int x, int y) {
    return (x > y) ? x : y;
}

int knapSack(int W, int w[], int v[], int n) {
    int i, wt;
    int K[n + 1][W + 1];
    for (i = 0; i <= n; i++) {
        for (wt = 0; wt <= W; wt++) {
            if (i == 0 || wt == 0)
                K[i][wt] = 0;
            else if (w[i - 1] <= wt)
                K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);
            else
                K[i][wt] = K[i - 1][wt];
        }
    }
    return K[n][W];
}

int main() {
    cout << "Enter the number of items in a Knapsack:";
    int n, W;
    cin >> n;
    int v[n], w[n];
    for (int i = 0; i < n; i++) {
        cout << "Enter value and weight for item " << i << ":";
        cin >> v[i];
        cin >> w[i];
    }
    cout << "Enter the capacity of knapsack";
    cin >> W;
    cout << knapSack(W, w, v, n);
    return 0;
}

なお、上記コードの int K[n + 1][W + 1]; や int v[n], w[n]; は可変長配列（VLA）と呼ばれる機能で、GCCなど一部のコンパイラでは動作しますが、C++の標準規格には含まれていません。移植性を高めたい場合は、std::vector<std::vector<int>> の使用を検討するとよいでしょう。

実行例

Enter the number of items in a Knapsack:4
Enter value and weight for item 0:10
50
Enter value and weight for item 1:20
60
Enter value and weight for item 2:30
70
Enter value and weight for item 3:40
90
Enter the capacity of knapsack100
40

この実行例では、4つの品物（価値10・重さ50／価値20・重さ60／価値30・重さ70／価値40・重さ90）が与えられ、ナップサックの容量は100です。この条件で得られる最大価値は 40 となります。これは、重さ90の品物を1つだけ選ぶのが最適であることを意味します。

計算量

このアルゴリズムの時間計算量・空間計算量はいずれも O(n × W) です。品物の数 n と容量 W に比例したサイズの表を一度埋めるだけで済むため、全探索（O(2^n)）と比べて大幅に高速に最適解を求められます。