Javaでのナップサック問題の実装

1.はじめに

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

2.ナップサック問題

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

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

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

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

3.数学的定義

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

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

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

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

この式では、M(n、w)は、重量制限wを持つn個のアイテムの最適解です。これは、次の2つの値の最大値です。

  • 重み制限wのn-1)個のアイテムからの最適解n番目のアイテムを除く)
  • 値がN番目の項目に加えてから最適解(N-1)商品及びWのマイナス重量N(含む番目の項目のn番目の項目)

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

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

int knapsackRec(int[] w, int[] v, int n, int W) { if (n  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  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で入手できます。