ナップザックですが正確な重量

Question

正確な重量Wを持つナップザックを決定するアルゴリズムはありますか？私。それは、それぞれが重みw_iと値v_iを持つn個のアイテムを持つ通常の0/1ナップザック問題のようなものです。すべてのアイテムの価値を最大化しますが、ナップザックのアイテムの総重量はで、正確には重量がWである必要があります！

私は「通常の」0/1ナップザックアルゴリズムを知っていますが、これは軽いが高い値のナップザックを返すこともできます。私は最高の値を求めるが、正確なWの重みを求めたい。ここで

は私の0/1ナップザック実装です：

public class KnapSackTest { 
    public static void main(String[] args) { 
     int[] w = new int[] {4, 1, 5, 8, 3, 9, 2}; //weights 
     int[] v = new int[] {2, 12, 8, 9, 3, 4, 3}; //values 

     int n = w.length; 
     int W = 15; // W (max weight) 

     int[][] DP = new int[n+1][W+1]; 

     for(int i = 1; i < n+1; i++) { 
      for(int j = 0; j < W+1; j++) { 
       if(i == 0 || j == 0) { 
        DP[i][j] = 0; 
       } else if (j - w[i-1] >= 0) { 
        DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j - w[i-1]] + v[i-1]); 
       } else { 
        DP[i][j] = DP[i-1][j]; 
       } 
      } 
     } 
     System.out.println("Result: " + DP[n][W]); 
    } 
} 

これは私に与える：

Result: 29 

（！何が私の質問に不明である場合だけで尋ねる）

Answer 1

を簡単に設定することにより、あなたの最後のelse句のDP[i][j] = -infinityはそれを行うでしょう。

その背後にあるのIDEは少し計算する再帰式の定義を変更することです：

• はアイテムiまで正確重量jと最大値を検索します。

さて、帰納法の仮定が変化し、正しさの証明は、以下の修正との定期的なナップザックに非常に似ています：

DP [I] [J-重量[I]]今あります最大値は正確にj-weight[i]で構成することができ、DP[i][j-weight[i]]の値を与えるiの項目を取るか、それを取らないで、DP[i-1][j]の値を与えます。これは、ちょうどjの最初のi-1の項目を使用するときの最大値です。

DP[i][j]を何らかの理由で構築できない場合、MAXを検索するときに常に値が破棄されるため、絶対に使用しないことに注意してください。