Как отследить путь в простой задаче динамического программирования?

Я пытаюсь решить простую проблему DP:

Учитывая положительное целое число n, вы можете выполнить любой из следующих 3 шагов. 1) Вычтите из него 1.
2) Если оно делится на 2, разделите на 2.
3) Если оно делится на 3, разделите на 3.
Найдите минимальное количество шагов, которое принимает n к 1 и распечатывает шаги. Если есть несколько решений для достижения цели за одинаковое количество шагов, распечатайте все эти решения. (если сложно, хотя бы распечатайте одно из этих решений).

Набрать минимальное количество шагов не так уж и сложно. Просто примените решение DP снизу вверх следующим образом:

public int getMinSteps(int n) {
int[] dp = new int[n+1];

int i;
dp[1] = 0; 

for( i = 2 ; i < = n ; i ++ ) {
dp[i] = 1 + dp[i-1];
if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );
if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );
}
return dp[n];
}

Однако мне не удалось решить часть пути печати. На высоком уровне, я думаю, мне нужно остановить «действие», на каждом уровне определяется минимум?

Надеюсь, я могу получить хорошее предложение или решение здесь.

Спасибо!


java algorithm dynamic-programming
person Eric H.    schedule 19.11.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Просто получите еще одно поле для хранения оптимального шага, то есть -1, /2 или /3, если оптимально получить минимальный путь, возможно, просто используя 1, 2, 3 в качестве индикаторов.

Например, вы сравниваете a = 1 + dp[i-1], b = 1 + dp[i/2], c = 1 + dp[i/3]. Если a минимально, то вы знаете, что должны -1 для числа. Сохраните шаг как 1. Позже вы просто переходите к полю для i-1, чтобы найти следующий шаг, пока не достигнете начальной точки, то есть 1.

Обновлять:

Если вы хотите распечатать все пути, вам нужно сохранить все оптимальные шаги и распечатать все комбинации.

В деталях вы можете использовать три логических поля для -1, /2, /3 для хранения, если какой-либо оптимальный путь проходит через определенное число. После этого вы можете печатать все комбинации рекурсивно, как обход дерева.

int[] dp; // for minimum steps
bool[] gominus1;
bool[] godivideby2;
bool[] godivideby3;
List<Integer> steps;

PrintAllPath(int n) {
    if(n == 1) {
        // print steps
        return;
    }
    steps.push_back(n);
    if(gominus1[n]) {
        PrintAllPath(n - 1);
    }
    if(godivideby2[n]) {
        PrintAllPath(n / 2);
    }
    if(govidivideby3[n]) {
        PrintAllPath(n / 3);
    }
    steps.pop_back();
}
person Dante May Code    schedule 19.11.2012
comment
спасибо за предложение. Я думаю, мне нужно найти правильную структуру данных для хранения этих шагов, поскольку, возможно, их много. Что еще сложнее, может быть несколько комбинаций шагов. - person Eric H.; 19.11.2012
comment
@ user1660652 это довольно просто. Смотрите обновление в ответе. - person Dante May Code; 19.11.2012

arrow_upward
1
arrow_downward

Вот как вы можете получить путь:

    public static int getMinSteps(int n) {
    int[] dp = new int[n + 1];
    String[] path = new String[n+1];
    int i;
    dp[1] = 0;
    path[1] = "end";

    for (i = 2; i <= n; i++) {
        dp[i] = 1 + dp[i - 1];
        if (i % 2 == 0) {

            if(dp[i] < 1 + dp[i/2]){
                path[i] = "sub 1," + path[i-1];
            }
            else {
               path[i] = "div by 2," + path[i/2];
            }

            dp[i] = min(dp[i], 1 + dp[i / 2]);

        }

        if (i % 3 == 0) {

             if(dp[i] < 1 + dp[i/3]){
                path[i] = "sub 1," + path[i-1];
            }
            else {
               path[i] = "div by 3," + path[i/3];
            }

            dp[i] = min(dp[i], 1 + dp[i / 3]);
        }

        if( i % 3 != 0 && i % 2 != 0) {
             path[i] = "sub 1," + path[i-1];
        }

    }
    System.out.println("number of steps = "+dp[n]+",path = "+path[n]);
    return dp[n];
}

Это для печати одного пути. Чтобы вывести весь путь, нужно отследить все минимально возможные пути к dp[i]. Поэтому вам нужен двумерный массив строк для их хранения.

person Sazzadur Rahaman    schedule 19.11.2012
comment
Спасибо - я думаю, что это будет работать идеально, если есть только одно оптимизированное решение. Однако для случаев, когда есть два или более оптимизированных решения, будет распечатано только одно из них. Например, если n=7, то мы можем сделать: (1) sub 1, div 2, div 3; или (2) подраздел 1, раздел 3, раздел 2. - person Eric H.; 19.11.2012
comment
Да, чтобы иметь все пути, нужно использовать двумерный массив переменных путей и хранить там все оптимальные комбинации. - person Sazzadur Rahaman; 19.11.2012