最小最远距离算法，实现问题

Question

我正试图实现一种算法，这需要几个距离和天数的路线，有人有时间^走这条路线。该算法应计算每天的最小最长距离。

我已经在数学课上问过了，因为我需要帮助找到数学函数。在那里你可以找到一个例子来更容易地理解我的意思。看到这里。

我尝试实现提议的递归函数:

Md(e1,…,en) = min{Md(e1,…,e′n−1), max{M d−1(e1,…,en−1), en}}

其中Md(e1,…,en)为所有分组中最长阶段的最小值，e1-en为距离，Md为d天的函数，假设Md(e1,e2,…,en)=max{e1,…,en}为d≥n

我尝试在这里实现这个:

private static int recursiveMin(int[] teilstrecken, int days)
    {
        List<int> tempList1 = new List<int>(teilstrecken);
        int last = tempList1.Last();
        tempList1.Remove(tempList1.Last());
        int vorletzter = tempList1.Last();
        List<int> tempList2 = new List<int>(teilstrecken);
        tempList1.Remove(tempList1.Last());
        tempList1.Add(last + vorletzter);
        tempList2.Remove(tempList2.Last());
        int[] array1 = tempList1.ToArray();
        int[] array2 = tempList2.ToArray();
        if (nEtappen >= teilstrecken.Length)
        {
            return array1.Max();
        }
        return Math.Min(recursiveMin(array1, days), Math.Max(recursiveMin(array2, days-1), last));
    }

但是这并没有返回我想要的结果。一个例子:

{64, 23, 56, 34, 23, 65, 28} in 3 Days应该返回113而不是90。

现在我要问，是我在实现中犯了错误，还是公式一开始就错了。有人知道吗?

Answer 1

首先，请给变量命名，这样你或其他人就能在6个月的时间里理解它们的含义;)

认为方法不太正确，在这里重做更容易:

private static int recursiveMin(int[] distances, int days) {
      // check for edge cases (single distance or one day)
      if(distances.length == 1) {
         return distances[0];
      }
      if(days == 1) {
         int sum = 0;
         for(int i=0;i<distances.length;i++) {
            sum += distances[i];
         }
         return sum;
      }
      // get the last distance
      int last = distances[distances.length - 1];
      // create the reduced array
      int[] oneLess = new int[distances.length - 1];
      for(int i=0;i<oneLess.length;i++) {
         oneLess[i] = distances[i];
      }
      // this is the max{M d−1(e1,…,en−1), en} part
      int right = Math.max( recursiveMin( oneLess, days - 1 ), last );
      // now use the reduced array again but add the last value on at the end
      oneLess[oneLess.length - 1] += last;
      // this is the Md(e1,…,e′n−1) part
      int left = recursiveMin( oneLess, days );
      return Math.min( left, right );
   }

它是在Java中完成的，但我相信如果你想的话，将其转换为c#是一个相当快的过程。它生成了两个示例的期望值，但还没有对其他任何情况进行测试，所以在期望它适用于每种情况之前，请确保对其进行测试!