WedX - журнал о программировании и компьютерных науках

Путь максимальной суммы Треугольник и получить числа, которые были добавлены С#

Я пытаюсь получить максимальную сумму от вершины до низа входного треугольника, которая должна быть такой

                      5
                    94 48
                   95 30 96
                 77 71 26 67
                97 13 76 38 45
              07 36 79 16 37 68
             48 07 09 18 70 26 06
           18 72 79 46 59 79 29 90
          20 76 87 11 32 07 07 49 18
         27 83 58 35 71 11 25 57 29 85
        14 64 36 96 27 11 58 56 92 18 55
       02 90 03 60 48 49 41 46 33 36 47 23
      92 50 48 02 36 59 42 79 72 20 82 77 42
     56 78 38 80 39 75 02 71 66 66 01 03 55 72
    44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
   85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93

Вывод должен быть:

Maximum total: 1320
Path (for example) : 55 - 48 -30 - etc

Путь должен быть числом, которое я сложил вместе, чтобы получить результат 1320. Я могу найти СУММУ (1320), но я не могу найти способ найти все числа, которые были суммированы. Мой код возвращает все числа, а не только те, которые были суммированы.

static void Sum()
    {
        int[,] list = new int[18, 19];
        int[,] list2 = new int[18, 19];

        string input = @"55
                        94 48
                       95 30 96
                     77 71 26 67
                    97 13 76 38 45
                  07 36 79 16 37 68
                 48 07 09 18 70 26 06
               18 72 79 46 59 79 29 90
              20 76 87 11 32 07 07 49 18
            27 83 58 35 71 11 25 57 29 85
           14 64 36 96 27 11 58 56 92 18 55
         02 90 03 60 48 49 41 46 33 36 47 23
        92 50 48 02 36 59 42 79 72 20 82 77 42
      56 78 38 80 39 75 02 71 66 66 01 03 55 72
     44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
   85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93";
        var charArray = input.Split('\n');

        for (int i = 0; i < charArray.Length; i++)
        {
            var numArr = charArray[i].Trim().Split(' ');

            for (int j = 0; j < numArr.Length; j++)
            {
                int number = Convert.ToInt32(numArr[j]);
                list[i, j] = number;
                list2[i, j] = number;
            }
        }

        StringBuilder path = new StringBuilder();
        for (int i = 16; i >= 0; i--)
        {
            for (int j = 0; j < 18; j++)
            {
                //list[i, j] = Math.Max(list[i, j] + list[i + 1, j], list[i, j] + list[i + 1, j + 1]);
                if (list[i, j] + list[i + 1, j] > list[i, j] + list[i + 1, j + 1])
                {
                    if (list2[i, j] > 0)
                        path.Append(list2[i, j] + " - ");
                    if (list2[i+1, j] >0)
                        path.Append(list2[i+1, j] + " - ");

                    list[i, j] = list[i, j] + list[i + 1, j];
                }
                else
                {
                    //path.Append(list2[i, j] + " - " + list2[i + 1, j + 1]+ " - ");
                    if (list2[i, j] > 0)
                        path.Append(list2[i, j] + " - ");
                    if (list2[i + 1, j] > 0)
                        path.Append(list2[i + 1, j] + " - ");

                    list[i, j] = list[i, j] + list[i + 1, j + 1];
                }
            }
        }

        Console.WriteLine(string.Format("Maximum total: {0} \n Path {1}", list[0, 0], path));

Я пытался в течение 4 дней решить эту проблему в течение 4 дней, но мне это не удалось, я ценю вашу помощь. Спасибо

c#
20.11.2019

  • Вы имеете в виду суммировать, построчно? 21.11.2019
  • Нет, я отредактирую 21.11.2019
  • @RufusL Хорошо. Но пожалуйста, не закрывайте его после редактирования, мне очень нужна помощь. 21.11.2019
  • Да, я скопировал его из своего проекта. 21.11.2019
  • @RufusL Я скопировал это снова. Пожалуйста, проверь это. Спасибо 21.11.2019

Ответы:


1

"...но я не могу найти способ найти все числа, которые были суммированы"

Вы так близко. Вы храните всю информацию, необходимую для построения пути через пирамиду. list выглядит так после вложенных циклов for. Можете ли вы придумать простой способ обойти list, чтобы найти путь?

1320 
1265 1130 
1171 1061 1082 
1076 1031 986  925  
999  903  960  813  858  
902  890  884  754  775  813  
895  854  805  682  738  694  745  
793  847  796  664  644  668  660  739  
719  775  717  618  585  543  589  631  649  
643  699  630  607  553  522  536  582  554  631  
566  616  512  572  482  466  511  509  525  509  546  
489  552  465  476  454  455  448  453  433  384  491  467  
487  445  462  416  383  406  364  407  400  348  342  444  426  
348  395  372  414  332  347  253  322  328  328  225  260  367  384  
292  220  317  334  293  272  216  251  245  262  204  224  257  312  292  
248  195  145  250  222  172  205  129  190  205  146  135  135  217  256  219  
33   163  120  98   165  124  121  94   75   143  98   129  134  62   118  167  108  
27   2    92   23   8    71   76   84   15   52   92   63   81   10   44   10   69   93   
21.11.2019
  • Нет. У меня есть исходные числа в объекте list2, но я не могу получить правильный путь. 21.11.2019
  • Вы должны строить путь по мере продвижения или вы можете построить его после завершения вложенных циклов? Если вам не нужно строить путь по мере продвижения, вы можете использовать оба списка для поиска пути. Начните с list[0,0]. Куда вы там ходите? list[1,0], так как это значение больше (1265 против 1130). Обратите внимание на индекс и извлеките значение из list2, которое имеет исходные значения. От 1265 куда вы идете? 1171. Снова используйте этот индекс, чтобы найти значение в list1. Продолжайте делать это, пока не доберетесь до дна, и у вас будет свой путь. 21.11.2019

  • 2

    Учитывая характер домашней работы вопроса, я ненавижу решать его прямо. Любой такой ответ окажет медвежью услугу вам и вашему учителю.

    Тем не менее, учитывая, что вы знаете о подходе динамического программирования, описанном на https://www.mathblog.dk/project-euler-18/, надеюсь, вам будет полезно дать некоторое представление о том, как должно выглядеть ваше решение, без фактического написания решения для вас.

    Итак, в частности, рассмотрим описанный алгоритм. Суть алгоритма в том, что он решает все подзадачи в нижней части вашего треугольника, складывая (или «сворачивая») результат из нижней строки в следующую строку выше.

    Важно отметить, что когда это делается, для каждого значения в следующей строке выше, которое обновляется, оно обновляется путем добавления одного или другого значения слева или справа от строки непосредственно ниже. Если вы хотите иметь возможность отображать путь, который максимальное решение проходит через треугольник, вам просто нужно помнить в каждой строке, из какого направления было рассчитано новое максимальное значение.

    Это легко сделать, введя новый массив с теми же размерами, что и исходный, но где вместо значений из ввода вы храните в массиве некоторое указание на то, было ли вычислено значение путем суммирования значения слева или справа. в строке ниже (естественно, этому массиву не потребуются какие-либо фактические данные в самой нижней строке, вы можете либо просто игнорировать значения там, либо вы можете сделать массив на одну строку меньше, чем исходный массив данных).

    Затем, как только вы закончите алгоритм и достигнете вершины числового массива, у вас также будет своего рода массив «хлебных крошек», который расскажет вам, как вы туда попали. Начиная с верхней строки, которая имеет только один элемент, вы можете просмотреть массив хлебных крошек, чтобы вспомнить, какой элемент из следующей строки был добавлен к этому элементу.

    С этой информацией вы теперь знаете, какой элемент из второй строки был использован. И массив хлебных крошек сообщает вам, какой элемент из строки ниже этой (третьей строки) был использован. И так далее.

    Есть и другие способы спроектировать структуру данных для достижения той же цели. Но все они сводятся к одной и той же основной идее: где-то хранить информацию о том, как была рассчитана каждая сумма, чтобы вы могли воспроизвести ее позже.

    Вам не составит труда изменить уже имеющийся код, включить этот дополнительный массив, а затем использовать его позже, чтобы вспомнить пройденный путь.


    Наконец, в духе аспекта динамического программирования, я укажу, что если вы строите свою выходную строку по мере продвижения, вам даже не нужен многомерный массив. Вместо этого вы просто начинаете с массива, содержащего строки, который имеет длину, равную предпоследней строке, и где первая строка, хранящаяся в каждом элементе массива, представляет собой просто число, которое было добавлено к текущему элементу в следующем ряду. -последний ряд.

    В каждой новой строке вы будете заменять каждую строку, добавляя (т. е. вставляя в начало) исходное число, которое было в позиции предыдущей строки, которая использовалась для текущей суммы. Вам нужно отслеживать исходный номер, что легко, потому что вы уже поддерживаете две копии массива в своем коде.

    И я отмечу, что этот метод «сохранить только одномерный массив» может работать и для промежуточных сумм. т.е. единственный двумерный массив, который вам действительно нужен, это тот, который содержит исходные данные. На каждой итерации вас интересует только самая последняя строка, поэтому вам просто нужен одномерный массив для этой строки.

    21.11.2019

    3

    Другой подход к динамическому программированию заключается в выполнении поиска в глубину, поскольку пирамида представляет собой просто дерево. Это соответствует методу «грубой силы», упомянутому в блоге @peterduniho. Основная идея очень проста: вы проверяете каждый путь от корня (55) до конечных узлов (27, 2 и т. д.).

    Я устанавливаю леса, чтобы вы могли двигаться. Вам может показаться, что с таким представлением данных немного проще работать, так как вам не нужно так много думать об индексах и ошибках, отличных друг от друга, и вы можете больше сосредоточиться на том, как решить проблему. Это также упрощает использование функций отладки Visual Studio (например, вы можете поставить точку останова в коде и просмотреть потомков и потомков потомков и т. д.).

    Если вы не знакомы с рекурсией, ключевой момент в коде, на который следует обратить внимание, это то, что DepthFirstSearch вызывает сам себя.

    (Я думаю, что динамическое программирование - лучший способ решить эту проблему, но я просто публикую это как альтернативу)

        public void Solve()
        {
            string input = 
                                    @"55
                                    94 48
                                   95 30 96
                                 77 71 26 67
                                97 13 76 38 45
                              07 36 79 16 37 68
                             48 07 09 18 70 26 06
                           18 72 79 46 59 79 29 90
                          20 76 87 11 32 07 07 49 18
                        27 83 58 35 71 11 25 57 29 85
                       14 64 36 96 27 11 58 56 92 18 55
                     02 90 03 60 48 49 41 46 33 36 47 23
                    92 50 48 02 36 59 42 79 72 20 82 77 42
                  56 78 38 80 39 75 02 71 66 66 01 03 55 72
                 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
               85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
              06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
            27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93";
    
            var tree = input.Split('\n')
                .Select(line => line.Trim()
                    .Split(' ')
                    .Select(s => new Node(int.Parse(s.Trim())))
                    .ToArray())
                .ToArray();
    
            for (var i = 0; i < tree.Length-1; i++)
            {
                for (var j = 0; j < tree[i].Length; j++)
                {
                    tree[i][j].Descendants.Add(tree[i + 1][j]);
                    tree[i][j].Descendants.Add(tree[i + 1][j+1]);
                }
            }
            var root = tree[0][0];
            int maxSum = 0;
            DepthFirstSearch(tree[0][0],  ImmutableList<Node>.Empty.Add(root), 0, ref maxSum);
        }
    
    
        private void DepthFirstSearch(Node root, ImmutableList<Node> path, int runningSum, ref int maxSum)
        {
            CheckBaseCase(root, path, ref maxSum);
            foreach(var node in root.Descendants)
            {
                runningSum += node.Value;
                DepthFirstSearch(node, path.Add(node), runningSum, ref maxSum);
            }
        }
    
        private void CheckBaseCase(Node root, ImmutableList<Node> path, ref int maxSum)
        {
            // Fill me in!
        }
    
       [DebuggerDisplay("Value = {Value}, DescendantCount={Descendants.Count}")]
       class Node
       {
           public Node(int value)
           {
               Value = value;
           }
           public int Value{ get; }
           public List<Node> Descendants { get; } = new List<Node>();
       }
    
    21.11.2019
  • Это Stack Overflow, а не Code Golf. На самом деле это не отвечает на вопрос, который был у ОП. Они конкретно ищут, как сообщить о пути через дерево в контексте решения динамического программирования. Метод грубой силы в любом случае непрактичен, потому что он не может масштабироваться так, как это делает версия с динамическим программированием, но даже если бы это было так, реализация грубой силы ничего не делает, чтобы помочь OP понять, как они могут исправить их реализацию. 21.11.2019
  • Отмеченный. Я пропустил явное требование для конкретного подхода. Ваше здоровье. 21.11.2019
  • Новые материалы

    Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что это выглядит сложно…
    Просто начните и учитесь самостоятельно Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что он кажется мне сложным, и я бросил его. Это в основном инструмент..

    Лицензии с открытым исходным кодом: руководство для разработчиков и создателей
    В динамичном мире разработки программного обеспечения открытый исходный код стал мощной парадигмой, способствующей сотрудничеству, инновациям и прогрессу, движимому сообществом. В основе..

    Объяснение документов 02: BERT
    BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..

    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..

    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..

    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..

    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..


    Для любых предложений по сайту: [email protected]