二维递归背包

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(); 
} 

使用哪种适合 - 第二是效率较低，因为它创造了许多新的瓦套和但它也有点整洁。