二維遞歸揹包

Question

假設我們有一個瓦片陣列，每個瓦片的大小爲n，還有一個2d陣列作爲板子。

我想寫一個遞歸函數，如果有可能適合棋盤上的所有瓷磚，則返回true，否則返回false（棋盤是否填充，只需要使用所有瓷磚）。

我嘗試了幾種方法失敗。

該解決方案不一定是最佳的。

Answer 1

我認爲貪婪算法策略可能適合您的需求。我發現了一個貪婪的aglorithm策略，在這裏遞歸實現：www.cs.siu.edu/~mcoleman/classwork/cs330bonus/Knapsack.java

我自己並沒有通過深入的解決方案來看看它是否會爲你工作。但是，我確信您可以選擇的一個潛在選項是貪婪算法策略。

Answer 2

您可以使用嵌套for循環遍歷2d數組中的每個空間來嘗試每個空間。

for(int x = 0; x < arraysizex; x++) 
{ 
    for(int y = 0; y < arraysizey; y++) 
     if(array[x][y] != filled) 
     { 
      //do something 
     } 
} 

Answer 3

請嘗試以下操作。您需要實現各種電路板實用功能，例如返回可能的電路板位置列表。我假設這是確定適合你 - 這是主要的遞歸搜索算法，你有興趣

boolean canFit(List<Tile> tiles, Board board) { 
    if (tiles.isEmpty()) { 
     return true; 
    } else { 
     for (Tile tile: tiles) { 
      tiles.remove(tile); 
      for (Position position: board.possiblePositionsFor(tile)) { 
       board.addTile(tile, position); 
       if (canFit(tiles, board)) 
        return true; 
       board.removeTile(tile); 
      } 
      tiles.add(tile); 
     } 
     return false; 
    } 
} 

的代碼將是整潔，如果你能在一個加磚創造新瓦套拆下瓦片和新板單一方法。然後，你可以擺脫所有的語句來改變瓦套和電路板，只是喜歡的東西取代了一切：

boolean canFit(TileSet tiles, Board board) { 
    return tiles.isEmpty() || 
     tiles.stream() 
      .flatmap(tile -> board.streamPossiblePositionsFor(tile) 
       .filter(pos -> canFit(tiles.remove(tile), board.add(tile, pos)) 
      .findAny().isPresent(); 
} 

使用哪種適合 - 第二是效率較低，因爲它創造了許多新的瓦套和但它也有點整潔。