Подход к проекту Euler # 18

Ответ 1

Это что-то называемое динамическим программированием.

У вас есть такой треугольник:

   3
  7 4
 2 4 6  
8 5 9 3

Когда вы перемещаетесь снизу вверх, вы можете рассчитать лучший выбор на последней итерации. В этом случае вы берете последнюю строку 8 5 9 3 и увеличиваете сумму в дополнение к предыдущей строке.

Итерация 1: Предположим, что вы находитесь на шаге last-1.

У вас есть строка 2 4 6, итерация на ней.

От 2 вы можете перейти на 8 или 5, поэтому лучше 8 (максимизируйте результат из 2), чтобы вы вычислили первая сумма 8 + 2 = 10.

От 4 вы можете перейти на 5 или 9, поэтому лучше 9 (максимизируйте свой результат из 4), чтобы вы вычислили вторая сумма 9 + 4 = 13.

От 6 вы можете перейти к 9 или 3, поэтому 9 лучше (максимизируйте свой результат с 6), чтобы вы вычислить третью сумму 9 + 6 = 15.

Это конец первой итерации, и вы получили строку сумм 10 13 15.

Теперь у вас есть треугольник меньшего размера:

    3
  7  4
10 13 15  

Теперь продолжайте, пока не получите одно значение, которое равно 23.

Ответ 2

Разница не между нисходящим и восходящим. Разница между жадным и "пограничным" методами.

Жадный алгоритм не обязательно поможет вам, потому что вы не сможете восстановиться, если лучшая часть дерева окажется вне досягаемости. Например: жадный алгоритм выбирает путь 1-3 сверху вниз. Это пропустит 9 полностью.

    1
   2 3
  9 1 1

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

Подход "снизу вверх" , как описано, не имеет этой проблемы. Он исследует не более n * (n-1) путей: 2 для каждого элемента. Однако, называя его подход "снизу вверх" , вводит в заблуждение.

Почему? Потому что есть подход сверху вниз, который эквивалентен. Суть в том, что у вас есть своего рода "граница" с лучшими результатами для всех деревьев за границей. Перемещение границы вверх или вниз является вторичным. Для подхода сверху вниз в приведенном выше примере вы вычисляете для каждой строки сумму каждого элемента и максимум двух лучших итоговых значений над ним:

     1
    3 4
  12 5 5

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

  9  1 1
   11 4
    12

В обоих подходах "сверху вниз" и "снизу вверх" существует равная работа.

Ответ 3

Используя ваш пример, подход "снизу вверх" подходит к нему:

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

8,5,9,3

Изучая следующую строку, большинство из которых вы можете получить из каждого элемента (в зависимости от того, вы идете слева или справа от него):

2 + max (8,5), 4 + max (5,9), 6 + max (9,3) = 10,13,15

Итак, это здорово; мы удалили 2 строки, сжимая их вместе, чтобы заменить их на одну строку, уменьшив проблему до

     3
   7   4
10  13  15

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

7 + max (10,13), 4 + max (13,15) = 20,19

Итак, из верхней части, вы можете получить максимум

3 + max (20,19) = 23

QED.

Ответ 4

На самом деле вам не нужно начинать снизу вверх; вы можете также начать сверху вниз, предоставляя вам это правильно.

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

    x
   x x
  x h x
 x y y x
x y y y x

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

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

Теперь это принимает O (N) (N означает число чисел), потому что для каждого места вы просто рассматриваете два пути и используете предварительно вычисленные значения с более низкого уровня.

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

best_length(node)
{ 
  if(node is terminal)
    return value(node)
  int m = 0
  for(next : lower neighbors of node)
    m = max(best_length(next), m)
  return m + value(node);
}

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

Ответ 5

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

Поскольку вы быстрее устраняете плохие пути, поиск по ширине становится оптимальным решением. Поиск по глубине в любом направлении является неправильным (как вы показали) и медленным.

Ответ 6

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

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

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

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

BFS имеет время работы O (| E | + | V |).
В треугольнике есть 1 + 2 + 3 + 4 + 5 +.. + n = (1/2) (n) (n-1) узлы
Это означает, что существуют (n) (n-1) пути, плюс (n) для окончательного соединения node
Всего: (1/2) (3n ^ 2 -n), где n - количество строк.

Ответ 7

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

import sys
def max_sum(i,j):
    if i==14:
        return a[i][j]
    return a[i][j]+max(max_sum(i+1,j),max_sum(i+1,j+1))
a=[]
for i in range(15):
    b=list(map(int,sys.stdin.readline().split()))
    a.append(b)
print(max_sum(0,0))

для вопроса 67 - (Максимальная длина пути II) вы можете использовать memoisation:

import sys
d={}
def max_sum(i,j):
    if (i,j) in d:
        return d[(i,j)]
    if i==99:
        return a[i][j]
    d[(i,j)]=a[i][j]+max(max_sum(i+1,j),max_sum(i+1,j+1))
    return d[(i,j)]
a=[]
for i in range(100):
    b=list(map(int,sys.stdin.readline().split()))
    a.append(b)
print(max_sum(0,0))

Ответ 8

Вот полный ответ:

#include <iostream>

using namespace std;

int main()
{
  int sum1,sum2;
  int A[4][4] = {{3,0,0,0},{7,4,0,0},{3,4,6,0},{8,5,9,3}};
  for(int i=2;i>=0;i--){
     for(int j=0;j<4;j++){
        sum1=A[i][j]+A[i+1][j];
        sum2=A[i][j]+A[i+1][j+1];
        if(sum1>sum2){
            A[i][j]=sum1;
        }
        else{
            A[i][j]=sum2;
        }
     }
  }
  cout<<A[0][0]<<endl;
}

Ответ 9

static int getTriangle() throws FileNotFoundException, IOException{
        File file = new File("/home/rakib/This Pc/programming/problem solving/ProjectEuler/src/projecteuler/euluer17.txt");
        BufferedReader br = new BufferedReader(new FileReader(file));
        String n;
        int i = 0;
        int [][] array = new int[15][15];
        while((n = br.readLine()) != null){
            String [] temp = n.split(" ");
            for(int j = 0; j < temp.length; j++){
                 array[i][j] = Integer.parseInt(temp[j]);         
            }
             i++;
        }


    for(int j = array.length-2; j >= 0; j--){
        int []tempArray = new int [j+1];
           for(int k =0; k <= j; k++){
               tempArray[k] = array[j][k] + Math.max(array[j+1][k], array[j+1][k+1]);
           }
           array[j] = tempArray;
    }

 return array[0][0];
}

Я использовал подход снизу вверх, чтобы решить эту проблему. работает с последних двух строк. просто добавьте максимальное значение с элементом пути.