ナップザック0-1パス再構築

Question

私はダイナミックプログラミングアプローチでナップザック0-1の問題を解決する方法を知っていますが、どのアイテムをO（N * C）（N個のアイテム、Cの容量）。

アイデア（私はボトムアップアプローチを好むだろう）？

Answer 1

今のところ、配列bool[] aに結果を格納しているとします。iの場合はa[i]が真となります。
別の配列int[] bが必要です。を達成するためには、b[i]がナップザックに配置された最後の要素です。

だから、あなたが次に

a[i] = true; 
b[i] = current_item; 

が必要になります

a[i] = true; 

を持っていたところ、アイテムが合計iを達成するために撮影することができます発見は、単純なループです。

PS簡潔にするために2つの配列を使用していますが、明らかに配列aは削除できます。ここで

Answer 2

boolean[] solution = new boolean[nItems]; 

for (int i = nItems, c = maxCapacity; i > 0 && c > 0; i--) { 
    int iThItemAddedValue = value[i - 1][c - weights[i - 1]] + values[i - 1]; 
    int iThItemInheritedValue = value[i - 1][c]; 

    if (iThItemAddedValue > iThItemInheritedValue) { 
     solution[i - 1] = true; 
     c = c - weights[i - 1]; 
    } else { 
     solution[i - 1] = false; 
    } 
} 

Answer 3

はOパスを再構築するための変更は、（N）倍

int knapsack(int weight[], int profit[], int no_of_items, int capacity) { 
    for (int var = 0; var <= capacity; ++var) { 
     dp[0][var] = 0; 
    } 
    for (int var = 0; var <= no_of_items; ++var) { 
     path[var] = false; 
    } 
    int using_item_i, without_using_item_i; 
    for (int i = 1; i <= no_of_items; ++i) { 
     for (int j = 1; j <= capacity; ++j) { 
      without_using_item_i = dp[i - 1][j]; 
      using_item_i = 0; 
      if ((weight[i]) <= j) { 
       using_item_i = dp[i - 1][j - weight[i]] + profit[i]; 
      } 

      if (using_item_i >= without_using_item_i) { 
       taken[i][j] = true; 
       dp[i][j] = using_item_i; 
      } else { 
       taken[i][j] = false; 
       dp[i][j] = without_using_item_i; 
      } 
     } 
    } 
    //Reconstructing back the path 
    int j = capacity; 
    for (int i = no_of_items; i >= 0; --i) { 
     if (taken[i][j]) { 
      path[i] = true; 
      cnt++; 
     } 
     j = j - weight[i]; 
    } 
    return dp[no_of_items][capacity]; 
} 

Answer 4

https://www.dropbox.com/s/ish7t5vgy91fovt/Screenshot%202017-01-01%2015.16.31.png?dl=0

呼び出し側で印刷tmpListで、あなたは答え

Answer 5

が確認取得します添付画像のゾル

Answer 6

public class Knapsackproblem { 
    private static int[][] cache; 
    public static void main(String[] args) { 
     int val[] = new int[]{60, 100, 120}; 
     int wt[] = new int[]{10, 20, 30}; 
     int W = 50; 
     int n = val.length; 
     System.out.println(knapSack(W, wt, val, n)); 
     printValues(wt,val); 
    } 

    /** 
    * This method will find the result with 
    * more value with weight less than or equal 
    * to given weight 
    * @param w given weight 
    * @param wt arrays of weights 
    * @param val array of values 
    * @param n length of the array 
    * @return max value we can obtain 
    */ 
    private static int knapSack(int w, int[] wt, int[] val, int n) { 
    cache = new int[n+1][w+1]; 
     for (int i = 1; i <= n; i++) { 
      for (int j = 1; j <= w; j++) { 
       if(j < wt[i-1]){ 
        cache[i][j] = cache[i-1][j]; 
       }else { 
        cache[i][j] = Math.max(cache[i-1][j],(cache[i-1][j-wt[i-1]])+val[i-1]); 
       } 
      } 
     } 
     for (int[] aCache : cache) { 
      System.out.println(Arrays.toString(aCache)); 
     } 
     return cache[n][w]; 
    } 

    private static void printValues(int[] wt, int[] val) { 
     int m = cache.length-1; 
     int n = cache[0].length-1; 
     util(wt,val,m,n); 
    } 

    private static void util(int[] wt, int[] val, int m, int n) { 
     if(m <=0 || n<=0) return; 
     if((cache[m][n] != cache[m-1][n]) && (cache[m][n] != cache[m][n-1])){ 
      System.out.println(val[m-1]+"-->"+wt[m-1]); 
      util(wt, val, m-1, (n - wt[m - 1] + 1)); 
     }else 
     if(cache[m][n] == cache[m-1][n]){ 
      util(wt,val,m-1,n); 
     } 
     else if(cache[m][n] == cache[m][n-1]) 
      util(wt,val,m,n-1); 
     else 
      util(wt,val,m,(n-val[m-1]+1)); 
    } 
}