C++で0/1ナップサック問題を解き、選ばれたアイテムを出力する方法

n個のアイテムの重さと価値が与えられたとき、容量Wのナップサックに収まる範囲で合計価値が最大になるようにアイテムを選び、実際に選ばれたアイテム(重さ)を出力するのが本記事の目的です。

0/1ナップサックとは?

ナップサックとは、サイズや耐えられる重量が固定された袋のことです。ナップサックに入れる各アイテムには、それぞれ価値(利益)と重さがあります。ナップサックが保持できる総重量の範囲内で、利益が最大になるようにアイテムを選ぶ必要があります。

各アイテムの重さ、価値(利益)、そしてナップサックが保持できる総重量が分かっているとき、0/1ナップサックでは各アイテムを「入れる(1)」か「入れない(0)」かで表現します。0はナップサックに入れられないアイテム、1はナップサックに含められるアイテムを意味します。アイテムを分割して入れることはできず、「全部入れる」か「全く入れない」かの二択である点が特徴です。

簡単な例で理解しよう

val[] = {1, 2, 5, 6} // 価値または利益
wt[] = {2, 3, 4, 5}  // 重さ
W = 8                // 容量

このときのナップサック表は、次の漸化式を使って埋めることができます。

K[i, w] = max{K[i−1, w], K[i−1, w−wt[i]] + val[i]}

この式は「i番目のアイテムを入れない場合の価値」と「i番目のアイテムを入れた場合の価値」を比較し、大きい方を採用することを意味します。完成した表をバックトラッキング(遡り)の手法でたどると、どのアイテムが選ばれたのかを特定できます。

• K[n][w]からバックトラッキングを開始します。ここでK[n][w]は8です。
• 表を上方向にたどっていくと、8は4行目にのみ存在するため、4番目のアイテムが採用されています。つまり、4番目のアイテムを追加することで最大利益が得られます。
• 合計利益8から、4番目のアイテムの利益6を引くと2になります。
• さらに表を遡って、最大利益が2になる場所を探すと、それは2番目のアイテムを追加したときです。
• したがって、2番目と4番目のアイテムをナップサックに入れることで、容量を効率的に使い、最大利益を達成できます。

入出力例

入力: val[] = {60, 100, 120}
      wt[] = {10, 20, 30}
      w = 50
出力: 220   // 最大価値
      30 20 // 選ばれた重さ
説明: 最大重量50に到達するため、価値120の重さ30と、
      価値100の重さ20の2つのアイテムを選びます。

入力: val[] = {10, 40, 50}
      wt[] = {2, 4, 5}
      w = 6
出力: 50
      4 2
説明: 最大重量6に到達するため、価値40の重さ4と、
      価値10の重さ2の2つのアイテムを選びます。

アルゴリズム

開始
ステップ1 -> 関数 max(int a, int b)
    戻り値: (a > b) ? a : b
ステップ2 -> 関数 printknapSack(int W, int wt[], int val[], int n)
    変数 i, w および表 K[n + 1][W + 1] を宣言する
    // ボトムアップ方式で表 K[][] を構築する
    i = 0 から i <= n まで繰り返し(i++)
        w = 0 から w <= W まで繰り返し(w++)
            もし i == 0 または w == 0 ならば
                K[i][w] = 0 を設定
            そうでなく wt[i - 1] <= w ならば
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]) を設定
            それ以外ならば
                K[i][w] = K[i - 1][w] を設定
    // ナップサックの結果を保存する
    res = K[n][W] を設定
    res を出力する
    w = W を設定
    // バックトラッキングで選ばれたアイテムを特定する
    i = n から i > 0 かつ res > 0 の間繰り返し(i--)
        もし res == K[i - 1][w] ならば
            continue(そのアイテムは未採用なので次へ)
        それ以外ならば
            wt[i - 1] を出力する
            res = res - val[i - 1] を設定
            w = w - wt[i - 1] を設定
ステップ3 -> 関数 int main()
    val[] = { 50, 120, 70 } を設定
    wt[] = { 10, 20, 30 } を設定
    W = 50 を設定
    n = sizeof(val) / sizeof(val[0]) を設定
    printknapSack(W, wt, val, n) を呼び出す
終了

バックトラッキングの判定ロジックはシンプルです。res == K[i-1][w]が成り立つ場合、i番目のアイテムを入れなくても同じ価値が得られるため、そのアイテムは未採用と判断できます。逆に価値が異なる場合は、i番目のアイテムが採用されていることになるので、その重さを出力し、残りの価値と容量を更新して処理を続けます。

C++実装例

#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
// 容量Wのナップサックに入れるアイテムを出力する
void printknapSack(int W, int wt[], int val[], int n) {
    int i, w;
    int K[n + 1][W + 1];
    // 表K[][]をボトムアップ方式で構築する
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] +
                    K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
    // ナップサックの結果を保存する
    int res = K[n][W];
    printf("maximum value=%d\n", res);
    w = W;
    printf("weights included\n");
    for (i = n; i > 0 && res > 0; i--) {
        if (res == K[i - 1][w])
            continue;
        else {
            printf("%d ", wt[i - 1]);
            res = res - val[i - 1];
            w = w - wt[i - 1];
        }
    }
}
// メインコード
int main() {
    int val[] = { 50, 120, 70 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    printknapSack(W, wt, val, n);
    return 0;
}

出力

maximum value=190
weights included
30 20

この例では、価値50の重さ10、価値120の重さ20、価値70の重さ30という3つのアイテムから、容量50のナップサックに対して最適な組み合わせを求めています。その結果、重さ30と重さ20のアイテムを選ぶことで、最大価値190が達成されました。

計算量について

この動的計画法によるアプローチの時間計算量はO(n×W)、空間計算量もO(n×W)となります。ここでnはアイテム数、Wはナップサックの容量です。なお、サンプルコードでは可変長配列(VLA)を使用していますが、これはC++の標準規格外の機能のため、移植性を高めたい場合はstd::vector<std::vector<int>>などで表を確保すると安全です。