Простая динамическая программа программирования

Question

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

Например для ввода

1 
6 5 
3 1 7 4 2 
2 1 3 1 1 
1 2 2 1 8 
2 2 1 5 3 
2 1 4 4 4 
5 2 7 5 1 

вывод должен быть 32, но мой код выхода 20.

Мой подход был исчерпывающе попробовать все возможные маршруты через поле следующим образом:

 y == last_row return value[x,y] 
f(x,y) 
     y != last_row return value[x,y] + max(f(x-1,y+1),f(x,y+1),f(x+1,y+1)) 

Есть ли ошибка в моем подходе, в моем коде или в обоих случаях?

Код здесь:

#include <iostream> 
#include <vector> 
#include <limits> 

using namespace std; 

typedef int T; 

T max(T x, T y, T z) { 
    if(x < y) { 
     if(y < z) return z; 
     else return y; 
    } 
    else { 
     if(y > z) return x; 
     else { 
      if(x > z) return x; 
      else return z; 
     } 
    } 
} 

//Finds the maximum amount of stones possibly gathered by following coordinates x,y 
//The topmost left is (0,0), bottom right is (columns-1,rows-1) 
T max_stones_found_following(T x, T y, vector< vector<T> > A) { 
    //Reached the last row? 
    if(y == A.size()-1) return A[x][y]; 
    else { 
     T went_left, went_right, went_down; 
     if(x-1 >= 0) went_left = max_stones_found_following(x-1, y+1, A); 
     else went_left = numeric_limits<T>::min(); 
     if(x+1 <= A[x].size()-1) went_right = max_stones_found_following(x+1, y+1, A); 
     else went_right = numeric_limits<T>::min(); 
     went_down = max_stones_found_following(x, y+1, A); 
     return A[x][y] + max(went_left, went_right, went_down); 
    } 
} 

int main() { 
    //Initialization 
    T test_cases, rows, columns, stones_found, max_stones; 
    vector< vector<T> > A; 
    cin >> test_cases; 
    while(test_cases--) { 
     //Field input 
     cin >> rows >> columns; 
     for(int i = 0; i < rows; i++) { 
      vector<T> row; 
      for(int j = 0; j < columns; j++) { 
       T in; 
       cin >> in; 
       row.push_back(in); 
      } 
      A.push_back(row); 
     } 

     max_stones = 0; 
     stones_found = 0; 
     //Try starting at different positions in the first row 
     for(int i = 0; i < columns; i++) { 
      stones_found = max_stones_found_following(i, 0, A); 
      if(stones_found > max_stones) max_stones = stones_found; 
     } 

     //Output 
     cout << max_stones << endl; 
    } 
    return 0; 
} 

Answer 1

Некоторые из ваших проблем:

• Метод max является более сложным, что необходимо. Вы делаете много сравнения, чтобы найти максимум. Смотрите ниже.
• Вашей основная проблема использование i и j перевернутых, по данным сайта вызывающего i означает column, где начать в row 0 и в методе max_stones_found_following вы используете в качестве строки матрицы значений.

фиксированный код (кстати, это очень медленные решения для больших входных данных, а не динамическое программирование):

#include <iostream> 
#include <vector> 
#include <limits> 

using namespace std; 

typedef int T; 

T max(T x, T y, T z) { 
    return std::max(x, std::max(y, z)); 
} 

// Finds the maximum amount of stones possibly gathered by following coordinates 
// x,y 
// The topmost left is (0,0), bottom right is (columns-1,rows-1) 
T max_stones_found_following(T x, T y, vector<vector<T>> A) { 
    // Reached the last row? 
    if (y == A.size() - 1) 
     return A[y][x]; 
    else { 
     T went_left, went_right, went_down; 
     if (x - 1 >= 0) 
      went_left = max_stones_found_following(x - 1, y + 1, A); 
     else 
      went_left = numeric_limits<T>::min(); 
     if (x + 1 <= A[y].size() - 1) 
      went_right = max_stones_found_following(x + 1, y + 1, A); 
     else 
      went_right = numeric_limits<T>::min(); 
     went_down = max_stones_found_following(x, y + 1, A); 
     return A[y][x] + max(went_left, went_right, went_down); 
    } 
} 

int main() { 
    // Initialization 
    T test_cases, rows, columns, stones_found, max_stones; 
    vector<vector<T>> A; 
    cin >> test_cases; 
    while (test_cases--) { 
     // Field input 
     cin >> rows >> columns; 
     for (int i = 0; i < rows; i++) { 
      vector<T> row; 
      for (int j = 0; j < columns; j++) { 
       T in; 
       cin >> in; 
       row.push_back(in); 
      } 
      A.push_back(row); 
     } 

     max_stones = 0; 
     stones_found = 0; 
     // Try starting at different positions in the first row 
     for (int i = 0; i < columns; i++) { 
      stones_found = max_stones_found_following(i, 0, A); 
      if (stones_found > max_stones) 
       max_stones = stones_found; 
     } 

     // Output 
     cout << max_stones << endl; 
    } 
    return 0; 
} 

См определение dynamic programming. Он применим для решения проблем, которые:

• Можете переломить проблемы.
• И эти подзадачи перекрывают некоторые способы.

Ex: эта проблема может быть разделена на подзадачи, как, что это лучший путь от row 0 ->row i. Имея это в виду, проблема наилучшего пути к row i, зависит только от лучших путей до row i-1 и значений матрицы для строки ith. Используя это, вы расширяете решение до row i до достижения последней строки.

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

Исходный код (Динамическое программирование):

#include <algorithm> 
#include <iostream> 
#include <vector> 

typedef std::vector<int> row_t; 
typedef std::vector<row_t> matrix_t; 

int main() { 
    // Initialization 
    int test_cases, rows, columns; 
    matrix_t A; 
    std::cin >> test_cases; 
    while (test_cases--) { 
     std::cin >> rows >> columns; 
     for (int i = 0; i < rows; i++) { 
      row_t row(columns); 
      int in; 
      for (int j = 0; j < columns; j++) { 
       std::cin >> in; 
       row[j] = in; 
      } 
      A.push_back(row); 
     } 

     // Dynamic Programming Here 

     // For storage the best path until each cell 
     matrix_t best_A (rows, row_t(columns, 0)); 
     std::copy(A[0].cbegin(), A[0].cend(), best_A[0].begin()); 

     for (int i = 1; i < rows; i++) { 
      for (int j = 0; j < columns; j++) { 
       // right down 
       if (j > 0 && best_A[i - 1][j - 1] + A[i][j] > best_A[i][j]) { 
        best_A[i][j] = best_A[i - 1][j - 1] + A[i][j]; 
       } 
       // left down 
       if (j < columns - 1 && best_A[i - 1][j + 1] + A[i][j] > best_A[i][j]) { 
        best_A[i][j] = best_A[i - 1][j + 1] + A[i][j]; 
       } 
       // down 
       if (best_A[i - 1][j] + A[i][j] > best_A[i][j]) { 
        best_A[i][j] = best_A[i - 1][j] + A[i][j]; 
       } 
      } 
     } 

     // End Dynamic Programming 

     auto it = std::max_element(best_A[best_A.size() - 1].cbegin(), best_A[best_A.size() - 1].cend()); 
     // Output 
     std::cout << *it << std::endl; 
    } 
    return 0; 
} 

Как прокомментировал ранее вы можете рассчитать оптимальный путь к row i читает только первые i строки, вы можете сделать это на лету (при чтении, прочитать первые строки , вычислять лучшие стартовые позиции, читать вторую строку, вычислять лучший путь до каждого столбца второй строки и т. д.), это очень хорошо, если вход действительно, действительно большой.Вам также не нужно сохранять лучший путь до rows 1..i, вам нужно всего лишь вычислить last row и наилучшие пути расчета actual row.

Answer 2

Динамическое программирование - отличный способ подойти к этой проблеме. Но, как анонимный прокомментировал, вы не используете его или, по крайней мере, не в ясной форме.

Если у вас есть C столбцов, то есть C возможных исходные местоположений и C вторых мест, но есть 3*C - 2 пары (первый, второй). Способ использования динамического программирования - отметить природу Маркова и для каждой ячейки во второй строке, всех путей, заканчивающихся в этой ячейке, сохранить только один с лучшим счетом.

Затем для каждой дополнительной строки вы снова оцениваете пути 3*C - 2, сохраняя только C из них.

Повторяйте, пока не достигнете дна.

Реализация, вы должны иметь вектор C «лучших» путей к текущей строке и построить вектор C лучших путей к следующей строке. Затем следующая строка становится текущей строкой (используйте vector::swap). Каждый «путь» должен хранить как минимум накопленное значение, но сохранение истории посещенных мест также может быть приятным.

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

ПРИМЕЧАНИЕ: Использование динамического программирования здесь делает сложность R*C вместо C * 3^R

Это было на самом деле очень весело придумывать реальное решение. Предупреждение: указатели впереди!

#include <iostream> 
#include <sstream> 
#include <vector> 

void solve_one_case(); 

int main(int argc, char** argv) 
{ 
    /* driver */ 
    const std::string input = "6 5\n" 
           "3 1 7 4 2\n" 
           "2 1 3 1 1\n" 
           "1 2 2 1 8\n" 
           "2 2 1 5 3\n" 
           "2 1 4 4 4\n" 
           "5 2 7 5 1"; 
    std::stringbuf inputstream(input, std::ios_base::in); 
    auto const oldbuf = std::cin.rdbuf(); 
    std::cin.rdbuf(&inputstream); 
    solve_one_case(); 
    std::cin.rdbuf(oldbuf); 
    return 0; 
} 

void solve_one_case() 
{ 
    /* get board size from input */ 
    int rows = 1, columns = 1; 
    std::cin >> rows >> columns; 
    std::vector<char> route(rows * columns, '|'); 

    /* get first row from input */ 
    std::vector<int> current_row, prev_row; 
    current_row.resize(columns); 
    for(int& start_score : current_row) 
     std::cin >> start_score; 

    /* get all cells from input, solving */ 
    char* pRoute = &route[columns]; 
    for(int row = 1; row < rows; ++row) { 
     prev_row = current_row; 

     int cell = 0;; 
     for(int column = 0; column < columns; ++column) 
     { 
      std::cin >> cell; 
      if (column > 0 && prev_row[column-1] > current_row[column]) { 
       current_row[column] = prev_row[column-1]; 
       *pRoute = '\\'; 
      } 
      if (column + 1 < columns && prev_row[column+1] > current_row[column]) { 
       current_row[column] = prev_row[column+1]; 
       *pRoute = '/'; 
      } 
      current_row[column] += cell; 
      ++pRoute; 
     } 
    } 

    /* find best value in final row */ 
    int best_score = current_row[0], best_end = 0; 
    for(int i = 1; i < columns; ++i) { 
     if (best_score < current_row[i]) { 
      best_score = current_row[i]; 
      best_end = i; 
     } 
    } 

    std::cout << "Best score is " << best_score << "\n"; 

    /* backtrack along route */ 
    int route_column = best_end; 
    for(int row = 0; row < rows; ++row) { 
     char breadcrumb = '*'; 
     pRoute -= columns; 
     std::swap(pRoute[route_column], breadcrumb); 
     switch (breadcrumb) { 
     case '/': ++route_column; break; 
     case '\\': --route_column; break; 
     } 
    } 

    /* print routes */ 
    pRoute = &route[0]; 
    for(int row = 0; row < rows; ++row) { 
     std::cout.write(pRoute, columns); 
     pRoute += columns; 
     std::cout << '\n'; 
    } 

    std::cout << std::flush; 
} 

Выход:

Best score is 32 
||*|| 
|/|*\ 
//|\* 
/||*| 
||*|\ 
|/*||