以最低的能源成本过河-解网

问：

有一座桥有2条车道，每条车道有n块木板，每块木板上刻着一个数字，代表通过它所需的能源成本。您最多有 k 次机会从一条车道切换到另一条车道。如何选择路径，使能源成本最小化？

以上是问题场景。所以把它翻译成代码，我认为它的意思是：

There are 2 arrays, for example: 
CASE 1:                                      CASE 2:
            lane A  lane B                                lane A  lane B
 board5       5       4                         board5       2       4
 board4       9       5                         board4       9       5
 board3       3       4                         board3       3       4
 board2       5       1                         board2       5       1
 board1       1       3                         board1       1       3

在本例中，n = 5 ，假设 k = 2，这意味着我们最多可以切换 2 次车道。

SO:
The best path should be:
CASE 1:                                      CASE 2:
            lane A  lane B                                lane A  lane B
 board5               4                         board5       2       
 board4               5                         board4               5
 board3               4                         board3               4
 board2               1                         board2               1
 board1       1                                 board1       1

请注意，在上述情况下，我从泳道 A 开始，因为这是一个更好的答案，但我们可以从泳道 B 开始，就好像我们可以找到更好的路径一样！

当 n，k 是任何其他数字时，如何选择最佳路径？而且，在这个问题中，车道数始终是 2，但如果有 3 条或更多车道怎么办？

编辑1：我编写了一个方法来获取所有可能的路径，如下所示：

  static ArrayList<String> pathList = new ArrayList<String>();
  static int[][] arrayTree;  //store 2 arrays as one 2-demension array

  public static void findNext(int nextLevel, String path){
        if(nextLevel > arrayTree.length - 1){
            pathList.add(path);
            return;
        }
        for (int i = 0; i < arrayTree[nextLevel].length; i++) {
            if(i == 1 && path.length() != 0){
                path = path.substring(0, path.length() - 2);
            }
            path += arrayTree[nextLevel][i] + " ";
            findNext(nextLevel + 1, path);
        }
    }

下一步是找到所有开关不超过 k 次的路径，并找到一条成本最低的能量。

虽然这是解决问题的一种方式，但背后的想法是列举所有的可能性，然后进行计算。

但是，一定有一些更方便的方法，也许使用一些数据结构或算法或动态规划（用于决策过程）知识......

如果对这个问题有任何其他想法，请告诉我......多谢！

数组动态语言无关

@PrabhjotSinghKainth感谢您的回复..但关键是我不知道如何解决它。我所有的代码只是创建 2 个数组和一些变量。我认为没有必要在这里发帖......而且我在这里并不要求完整的代码解决方案，我只是想一些想法，然后我会自己做代码部分。

0赞 aka.nice 11/21/2019

那么，您将如何表示路径呢？一旦你解决了这个问题，你将如何评估这条道路的能量？一旦你解决了这个问题，你将如何生成不同的路径？一旦你解决了这个问题，你将如何在可能的路径中找到最小值？您将如何打印解决方案？有没有更短的算法（一种不迭代所有可能的解决方案的算法）？

0赞 ColinXu 11/21/2019

@aka.nice一棵树能解决你提到的所有问题吗？

0赞 aka.nice 11/21/2019

@ColinXu你的意思是一棵树，用于探索我猜想的所有可能的解决方案。如果您有 m 个通道，每个通道有 n 个板，则最多是 m^n 个可能的路径（如果考虑到 k 交换的限制，则更少）。如果它可能会变得很大，那么也许您不希望它们在内存中同时出现。IMO 你可以像 Javi 建议的那样将路径表示为数组，并找到一种方法在主迭代中动态生成不同的路径。但是有不止一种方法可以剥猫皮，所以你可以尝试这种选择。想想你将如何表示跳跃，并将跳跃限制在k。

答：

2赞 Javi Manzano 11/21/2019 #1

在我看来，您可能需要一种算法来计算所有可能的路径，同时考虑到开关的最大数量。我想说的是，您应该开始尝试在没有开关限制的情况下这样做，尝试获得所有可能的组合：

A-A-A-A-B、A-A-A-B-B、A-B-B-A-B、B-A-B-B-A-B-B-

如果您有多条车道，您可以切换到其他任何一条车道还是只切换到当前车道旁边的车道？这是你必须考虑的事情。

总而言之：从小事做起，将你的工作分成更容易实现的小任务。试着在一张纸上设计你的算法，画一些图表并在开始编码之前进行处理，而不清楚你必须做什么。流程图在这里应该会有所帮助。

我希望我的建议对您有所帮助。 PS：这个周末我会尝试自己解决这个问题。

public class CrossRiver {
static int minEnergy = Integer.MAX_VALUE;
static void minCrossEnergy(int arr[][], int totalEnergy, int currentLane, int step, int k, String result)
{
    if(step == arr[0].length) {
        if(totalEnergy < minEnergy) {
            minEnergy = totalEnergy;
            System.out.println("new min found: " + minEnergy + " result: " + result);
        }
        else {
            System.out.println("completed: " + totalEnergy + " result: " + result);
        }
    }
    else {
        minCrossEnergy(arr, totalEnergy + arr[currentLane][step], currentLane, step + 1, k, result + String.valueOf(currentLane));
        if (k > 0)
            minCrossEnergy(arr, totalEnergy + arr[1 - currentLane][step], 1 - currentLane, step + 1, step == 0 ? k : k - 1, result + String.valueOf(1 - currentLane));
    }
}

public static void main(String[] args)
{
    int arr[][] = {
            {1, 5, 3, 9, 5},
            {3, 1, 4, 5, 4},
    };
    minCrossEnergy(arr, 0, 0, 0, 2, "");
}
}

以最低的能源成本过河

Cross the river with minimum energy cost

评论

评论

评论