Java でナップザック問題を解決するためのコード例

この記事では主に、2 種類のナップサック (01 と完全なナップサック) を含む Java ナップサック問題解決のサンプル コードを紹介します。 2 つのバックパックのアイデアと実装方法がそれぞれ説明されており、困っている友人がそれについて学ぶことができます。

バックパック問題とは主に、特定の容量のバックパックと、特定の価値と重量を持つアイテムの数、アイテムの価値を最大化するためにバックパックに入れるアイテムを選択する方法を指します。 01バックパックとアンリミテッドバックパックに分かれており、ここでは主に各アイテムを1つまで配置できる01バックパックについて説明します。無限バックパックは01バックパックに換装可能。

まずアルゴリズムの主なアイデアについて話して、動的プログラミングを使用してそれを解決しましょう。 i 番目のアイテムがトラバースされるたびに、w[i] と v[i] に基づいてアイテムをバックパックに入れる必要があるかどうかが決定されます。つまり、与えられた n 個のアイテムについて、v[i] と w[i] をそれぞれ i 番目のアイテムの値と重量とし、C をバックパックの容量とします。 v[i][j] を、容量 j のバックパックに積み込むことができる最初の i 個のアイテムの最大値を表すものとします。すると、次の結果が得られます:

(1), v[i][0]=v[0][j]=0;
(2), v[i][j]=v[i-1; ][j] w[i]>j
(3)のとき、v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+ v[i]} j>=w[i]の場合

さて、私たちのアルゴリズムはこれら 3 つの結論式に基づいています。

1. 01 バックパック:

1. 2 次元配列メソッド

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[][] f = new int[n+1][m+1]; //f[i][j]表示前i个物品能装入容量为j的背包中的最大价值 
    int[][] path = new int[n+1][m+1]; 
    //初始化第一列和第一行 
    for(int i=0;i<f.length;i++){ 
      f[i][0] = 0; 
    } 
    for(int i=0;i<f[0].length;i++){ 
      f[0][i] = 0; 
    } 
    //通过公式迭代计算 
    for(int i=1;i<f.length;i++){ 
      for(int j=1;j<f[0].length;j++){ 
        if(weight[i-1]>j) 
          f[i][j] = f[i-1][j]; 
        else{ 
          if(f[i-1][j]<f[i-1][j-weight[i-1]]+val[i-1]){ 
            f[i][j] = f[i-1][j-weight[i-1]]+val[i-1]; 
            path[i][j] = 1; 
          }else{ 
            f[i][j] = f[i-1][j]; 
          } 
          //f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]); 
        } 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      for(int j=0;j<f[0].length;j++){ 
        System.out.print(f[i][j]+" "); 
      } 
      System.out.println(); 
    } 
    int i=f.length-1; 
    int j=f[0].length-1; 
    while(i>0&&j>0){ 
      if(path[i][j] == 1){ 
        System.out.print("第"+i+"个物品装入 "); 
        j -= weight[i-1]; 
      } 
      i--; 
    } 
  } 
}

の時間と空間の複雑さ上記のメソッドはどちらも O (N *V) の場合、時間計算量は基本的に最適化できなくなりますが、空間計算量は O(V) まで最適化できます。

まず、上記の基本的な考え方を実装する方法を考えてください。2 次元配列 f[i][0..V] のすべての値を計算するメイン ループ i=1..N が必要です。毎回。それでは、配列 f[0..V] を 1 つだけ使用する場合、i 番目のループが終了した後、f[v] が定義した状態 f[i][v] を表すことを保証できますか? f[i][v] は 2 つの部分問題 f[i-1][v] と f[i-1][v-c[i]] から再帰的に導出されます。 f[i][v ] であることを保証できますか。 (つまり、i 番目のメインループで f[v] がプッシュされたとき)、f[i-1][v] と f[i-1][v-c[i]] の値は次のようになります。得られる？実際、これには、f[v] がプッシュされたときに f[v-c[i]] が状態 f を保存することを保証するために、各メイン ループで v=V..0 の順序で f[v] をプッシュする必要があります。 [i -1][v-c[i]] 値。

疑似コードは次のとおりです:

0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 4 4 4 4 4 4 4 4 4 4 
0 0 0 4 4 4 4 4 8 8 8 8 8 
0 0 3 4 4 7 7 7 8 8 11 11 11 
0 0 3 4 4 7 7 7 8 9 11 12 12 
0 0 3 4 4 7 7 7 8 10 11 12 12 
第4个物品装入 第3个物品装入 第1个物品装入

文 f[v]=max{f[v],f[v-c[i]]} は、伝達方程式 f[i][v とまったく同じです。 ] =max{f[i-1][v],f[i-1][v-c[i]]}、現在の f[v-c[i]] は元の f[i-1][ と同等であるためv-c [i]]。 v の循環順序を上記の逆順序から順序に変更すると、f[i][v] となり、f[i][v-c[i]] から推測できますが、意味と矛盾します。この問題は別の問題ですが、重要なナップザック問題 P02 は最も単純な解法であるため、1 次元配列のみを使用して 01 のナップザック問題を解く方法を学ぶことが非常に必要です。

最適解を見つけることに関するナップザック問題の質問では、実際には 2 つの異なる質問方法があります。質問によっては、バックパックが正確に満杯になったときの最適解を必要とするものもありますが、バックパックが満杯である必要がない質問もあります。これら 2 つの質問を区別する実装方法の 1 つは、初期化中に違いを生み出すことです。

バックパックを正確に埋める必要がある最初の質問の場合、初期化中に f[0] が 0 であることを除き、他の f[1..V] は -∞ に設定され、最終的な f が保証されます。 [N]はバックパックを正確に満たす最適なソリューションです。

バックパックを埋める必要はないが、価格をできるだけ大きくしたい場合は、初期化中にすべての f[0..V] を 0 に設定する必要があります。

なぜですか？これは次のように理解できます。バックパックにアイテムを入れられない場合、初期化された f 配列は実際には正当な状態です。バックパックが正確に満杯である必要がある場合、容量が 0 のバックパックのみが値 0 の何もなく「正確に満たされる」可能性があります。他の容量のバックパックには法的な解決策はなく、未定義の状態になります。 、それらの値はすべて -∞ である必要があります。バックパックに荷物を詰める必要がない場合、どの容量のバックパックでも「何も詰めない」という法的な解決策があり、この解決策の値は 0 であるため、初期状態の値はすべて 0 になります。

2. 1次元配列メソッド(入力不要)

for i=1..N
  for v=V..0
    f[v]=max{f[v],f[v-c[i]]+w[i]};

output

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[] f = new int[m+1]; 
    for(int i=0;i<f.length;i++){   //不必装满则初始化为0 
      f[i] = 0; 
    } 
    for(int i=0;i<n;i++){ 
      for(int j=f.length-1;j>=weight[i];j--){ 
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      System.out.print(f[i]+" "); 
    } 
    System.out.println(); 
    System.out.println("最大价值为"+f[f.length-1]); 
  } 
}

3. 1次元配列メソッド(入力必須)

rrreええ 出力

0 0 3 4 4 7 7 7 8 10 11 12 12 
最大价值为12

2. バックパック一式

N 種類のアイテムと容量 V のバックパックがあります。各アイテムは無制限に利用可能です。 i 番目のアイテムのコストは c[i]、値は w[i] です。これらのアイテムの合計コストがナップザックの容量を超えず、それらの値の合計が最大になるように、どのアイテムをナップザックに詰めることができるかを見つけます。
しかし、私たちはより優れた O(VN) アルゴリズムを持っています。

O(VN)アルゴリズム

このアルゴリズムは一次元配列を使用します。最初に疑似コードを見てください:

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[] f = new int[m+1]; 
    for(int i=1;i<f.length;i++){   //必装满则f[0]=0,f[1...m]都初始化为无穷小 
      f[i] = Integer.MIN_VALUE; 
    } 
    for(int i=0;i<n;i++){ 
      for(int j=f.length-1;j>=weight[i];j--){ 
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      System.out.print(f[i]+" "); 
    } 
    System.out.println(); 
    System.out.println("最大价值为"+f[f.length-1]); 
  } 
}

この疑似コードとP01の疑似コードが一致していることがわかります。 v のループのみがあります。順序が違うだけです。

rreee

出力

25

总结

以上がJava でナップザック問題を解決するためのコード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。