1. 序章

ナップサック問題は、多くの用途がある組み合わせ最適化問題です。 このチュートリアルでは、Javaでこの問題を解決します。

2. ナップサック問題

ナップサック問題では、一連のアイテムがあります。 各アイテムには、重みと価値のある値があります。

これらのアイテムをナップザックに入れたいと思います。 ただし、重量制限があります。

そのため、総重量が重量制限を超えず、可能な限り総重量が大きいものを選択する必要があります。 たとえば、上記の例の最善の解決策は、5kgのアイテムと6kgのアイテムを選択することです。これにより、重量制限内で最大値が$40になります。

ナップサック問題にはいくつかのバリエーションがあります。 このチュートリアルでは、0-1ナップサック問題に焦点を当てます。 0-1ナップサック問題では、各アイテムを選択するか、取り残さなければなりません。アイテムの一部を受け取ることはできません。 また、アイテムを複数回受け取ることはできません。

3. 数学的定義

ここで、数学表記で0-1ナップサック問題を形式化します。 nアイテムのセットと重み制限Wが与えられた場合、最適化問題を次のように定義できます。

この問題はNP困難です。したがって、現在、この問題を解決するための多項式時間アルゴリズムはありません。 ただし、この問題には動的計画法を使用した疑似多項式時間アルゴリズムがあります。

4. 再帰的ソリューション

この問題を解決するには、再帰式を使用できます。

この式では、 M(n、w)は、重量制限wnアイテムの最適なソリューションです。 これは、次の2つの値の最大値です。

  • 重量制限がw(n-1)アイテムからの最適解( n 番目のアイテムを除く)
  • n 番目のアイテムの値に(n-1)アイテムからの最適解とwからnの重みを引いたもの- 5番目のアイテム( n 番目のアイテムを含む)

n 番目のアイテムの重量が現在の重量制限を超えている場合、それは含まれません。 したがって、上記の2つのケースの最初のカテゴリに含まれます。

この再帰式はJavaで実装できます。

int knapsackRec(int[] w, int[] v, int n, int W) {
    if (n <= 0) { 
        return 0; 
    } else if (w[n - 1] > W) {
        return knapsackRec(w, v, n - 1, W);
    } else {
        return Math.max(knapsackRec(w, v, n - 1, W), v[n - 1] 
          + knapsackRec(w, v, n - 1, W - w[n - 1]));
    }
}

各再帰ステップで、2つの次善のソリューションを評価する必要があります。 したがって、この再帰的ソリューションの実行時間は O(2n)。です。

5. 動的計画法ソリューション

動的計画法は、他の方法では指数関数的に困難なプログラミング問題を線形化するための戦略です。 サブ問題の結果を保存して、後で再計算する必要がないようにするという考え方です。

動的計画法で0-1ナップサック問題を解くこともできます。 動的計画法を使用するには、最初に、0からnおよび0からWの次元の2次元テーブルを作成します。 次に、ボトムアップアプローチを使用して、次の表を使用して最適なソリューションを計算します。

int knapsackDP(int[] w, int[] v, int n, int W) {
    if (n <= 0 || W <= 0) {
        return 0;
    }

    int[][] m = new int[n + 1][W + 1];
    for (int j = 0; j <= W; j++) {
        m[0][j] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) { 
            if (w[i - 1] > j) {
                m[i][j] = m[i - 1][j];
            } else {
                m[i][j] = Math.max(
                  m[i - 1][j], 
                  m[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
    }
    return m[n][W];
}

このソリューションでは、アイテム番号nと重量制限Wにネストされたループがあります。 したがって、実行時間は O(nW)です。

6. 結論

このチュートリアルでは、0-1ナップサック問題の数学的な定義を示しました。 次に、Java実装でこの問題の再帰的な解決策を提供しました。 最後に、動的計画法を使用してこの問題を解決しました。

いつものように、記事のソースコードはGitHubから入手できます。