長いリストの分割と各チャンクの最小合計の計算

Question

私は与えられた文字列（または整数のリスト）のすべてのサブ文字列とすべてのサブ文字列を抽出する3つの小さなプログラムに取り組んでいますそれらの要素の異なる組み合わせ。私は今それらを理解しています...

このように（私は）これらのプログラムを学習することで、パズルを解くことができるかどうかを確認することでした。ここにパズルがあります：

私はトレッキングをしており、私は6歩いている距離{ 11, 16, 5, 5, 12, 10 }3日以内に終了したいと言います。だから、1日目は5、5キロ、2日目は5キロ、5キロ、13日目は12キロと10キロにすることができます。

おそらく私は1日目、16日目、5日目に11キロしかできませんでした。 2日目は5キロメートル、3日目は12~10キロメートルである。

など。 。 。等。 。 。

私の目標は、この3日間のコースでの「最小」歩行距離を解決することです。したがって、この例では、1日目の11日と2日目の26日と3日目の22日には最大26が与えられ、実際には最小値は26です。これよりも良くなりません。

私が選択した3つのチャンク（日）の組み合わせに関係なく、毎日の歩行距離は26未満にはなりません。たとえば、1日目は11 + 16、2日目は5 + 5、 10日目の10日目、私は27の最大値を見ています。

しかし、私はかなりの日数である3のリスト要素を分割する方法を理解することはできません。それが4であれば、私は毎日任意の数の距離で4つのチャンクを持つことができました。分割された要素をすべて加算し、どの最大値が最小値として出るかを確認します。

私はこの時点で私にとって大きな負担になるかもしれないことを嬉しく思っています（私は以下のプログラムを理解することができます）が、これを理解して助けてくれるか任意の日数や歩行段階を処理できる関数を書いています。私がこれまでに生産することができたすべての

は

static void Main(string[] args) 
    { 
     string str = Console.ReadLine(); 

     for (int i = 1; i <= str.Length; i++) 
     { 
      for (int j = 0; j <= (str.Length - i); j++) 
      { 
       string subStr = str.Substring(j, i); 
       Console.WriteLine(subStr); 
      } 
     } 

     Console.ReadLine(); 
    } 



    static void Main(string[] args) 
    { 
     List<int> list = new List<int>() { 11, 16, 5, 5, 12, 10 }; 

     for (int i = 0; i <= list.Count-1; i++) 
     { 
      for (int j = 0; j <= list.Count-i; j++) 
      { 
       string subList = string.Concat(list.GetRange(i, j)); 
       Console.WriteLine(subList); 
      } 
     } 

     Console.ReadLine(); 
    } 



    static void Main(string[] args) 
    { 
     GetCombination(new List<int> { 11, 16, 5, 5, 12, 10 }); 

     Console.ReadLine(); 
    } 

    static void GetCombination(List<int> list) 
    { 
     double count = Math.Pow(2, list.Count); 

     for (int i = 1; i <= (count-1); i++) 
     { 
      string str = Convert.ToString(i, 2).PadLeft(list.Count, '0'); 

      for (int j = 0; j < str.Length; j++) 
      { 
       if (str[j] == '1') 
       { 
        Console.Write(list[j]); 
       } 
      } 

      Console.WriteLine(); 
     } 
    } 

Answer 1

この問題はdynamic programmingによって解決することができます...すべてのサブリストおよびこれらの6歩行段階の組み合わせを印刷できる機能です。あなたはトリプル(day,prevDayDistance,daysLeft)ためMinDistance結果をキャッシュ検討することができ、大きな入力アレイの場合

class Program 
{ 
    static void Main(string[] args) 
    { 
     int[] array = { 11, 16, 5, 5, 12, 10 }; 
     // change last parameter to the number or days 
     int min = MinDistance(array, 0, 0, 3); 
     Console.WriteLine(min); 
    } 

    static int MinDistance(int[] array, int day, int prevDayDistance, int daysLeft) 
    { 
     if (day == array.Length) 
     { 
      return prevDayDistance; 
     } 
     if (daysLeft == 0) 
     { 
      return int.MaxValue; 
     } 

     // Keep walking. 
     int keepWalkResult = MinDistance(array, day + 1, prevDayDistance + array[day], daysLeft); 

     // Postpone it to the next day. 
     int sleepResult = MinDistance(array, day, 0, daysLeft - 1); 

     // Choose the best solution. 
     return Math.Min(keepWalkResult, Math.Max(prevDayDistance, sleepResult)); 
    } 
} 

：ここでは、トップダウン・アプローチとのそれのための私のコードです。