使用Java迭代2D數組8

這是0-1揹包問題的實現。問題聲明如下所示：使用Java迭代2D數組8

給出了兩個數組，一個包含一組項目的權重，另一個包含各權值的值。你提供了一個最大重量。在限制最大重量的情況下，通過選擇或不選擇項目組來確定可以獲得的最大值。值和權重列表將始終具有相同的大小。

這是我的解決方案，它通常工作正常（不在邊緣情況下）。

public static int getCombination(int[] weights, int[] values, int maxWeight){ 

     int[][] memo = new int[weights.length][maxWeight + 1]; 
     for (int i = 0; i < memo.length; i++) { 
      for(int j=0; j < memo[i].length; j++){ 
      if(j == 0){ 
       memo[i][j] = 0; 
      }else if(weights[i] > j){ 
       if(i == 0) memo[i][j] = 0; 
       else memo[i][j] = memo[i-1][j]; 
      }else{ 
       if(i == 0){ 
       memo[i][j] = values[i]; 
       } 
       else{ 
       memo[i][j] = Integer.max((values[i] + memo[i-1][j- weights[i]]), memo[i-1][j]); 
       } 
      } 
      } 
     } 
     return memo[weights.length -1][maxWeight]; 
     }

現在我想用Java 8 Streams和lambdas以聲明方式重寫這個完整的邏輯。有人可以幫助我。

來源

2017-05-15 Melissa Stewart

當然。你嘗試了什麼？ – Eugene

我試着使用flatMaps迭代循環，但是這並沒有真正的幫助，因爲我努力訪問索引值正在填充備忘錄。關鍵在於，我不知道如何開始。 –

順便說一句，你的方法很好。如果你不想並行化這個，你很好。

這裏是一個可能的出發點，以創建索引到你的數組：既然你的循環基礎的解決方案是完全沒問題

 int rows = 3; 
     int cols = 4; 
     int[][] memo = new int[rows][cols]; 
     IntStream.range(0, rows * cols).forEach(n -> { 
      int i = n/cols; 
      int j = n % cols; 

      System.out.println("(" + i + "," + j + ")"); 
     });

來源

2017-05-15 21:11:32

，流在這裏不增加多少價值，如果你只轉換爲循環來的forEach流。

如果您使用IntStream和toArray方法，您可以更多地使用流，因爲您可以專注於基於行和列索引計算值，而不關心將其填充到數組中。

int[][] memo = IntStream.range(0, rows) 
         .mapToObj(r -> IntStream.range(0, cols) 
               .map(c -> computeValue(r, c)) 
               .toArray()) 
         .toArray(int[rows][cols]::new);

在這裏，我們爲每一行創建一個數組，然後將這些數組放入一個2D數組中。如您所見，toArray()方法負責填充陣列。實際上，現在我已經看到了你的方法來更密切地計算這些值，但是我意識到如果在這種情況下不是不可能使用流，那麼流可能很困難。問題是你需要來自以前的列和行的值來計算當前值。這在我的解決方案中是不可能的，因爲我們只在最後創建數組。更具體地說，我的方法是無狀態的，即你不記得以前迭代的結果。

你可以看看你是否可以用Stream.reduce()來實現你的目標。

來源

2017-05-16 09:11:28

使用Java迭代2D數組8

回答

相關問題