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

Question

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

Чтобы лучше объяснить мой вопрос, давайте рассмотрим проблему с ранцем.

---

Пусть будет 3 пункта следующим образом:

        I1      I2      I3
---------------------------
Val     5       4       3     

Weight  4       5       2

Здесь оптимальный путь - это пункты, которые должны быть выбраны для оптимального решения.

Соотношения повторения следующие:

Let n be the nth item 
let c be the remaining capacity in the knapsack

f(n, c) = 0             // if n=0
f(n, c) = f(n-1, c)     // if weight[n] > c
f(n, c) = max(f(n-1, c), value[n] + f(n-1, c-weight[n]))  // if weight[n] <= c

Я написалРешение DP на основе этого рекуррентного отношения (в java) без какой-либо оптимизации пространства следующим образом:

public static void main(String[] args) {
    int[] value = {5, 4, 3};
    int[] weight = {4, 5, 2};

    int capacity = 9;


    int[][] dp = new int[value.length+1][capacity+1];

    for(int i=0; i<=value.length; i++) {
        for(int j=0; j<=capacity; j++) {
            if(i==0) {
                dp[i][j] = 0;
            } else {
                if(weight[i-1] <= j){
                    dp[i][j] = Math.max(dp[i-1][j], value[i-1] + dp[i-1][j - weight[i-1] ]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
    }

    System.out.println("optimal value is: " + dp[value.length][capacity]);
}

Это печатает оптимальное решение, равное 9.

Теперь я хочу найти, какие элементысоставьте оптимальное решение (в данном случае это будет I1, I2).

Я использую следующую логику:

1. Матрица dp [] [] выглядит следующим образом:

   0 0 0 0 0 0 0 0 0 0
   0 0 0 0 5 5 5 5 5 5
   0 0 0 0 5 5 5 5 5 9
   0 0 3 3 5 5 8 8 8 9

2. Строка 4 (индекс 3) в dp [] [] соответствует пункту 3, поэтому я сравниваю dp [3] [9] (правый нижний угол)й дп [2] [9].Поскольку оба значения одинаковы, я знаю, что пункт 3 не был выбран .Я иду в дп [2] [9].

3. Я сравниваю дп [2] [9] с дп [1] [9].Поскольку значения разные, я знаю пункт 2 был выбран .Я иду на dp [1] [9 - вес предмета 2] => dp [1] [4].
4. Я сравниваю dp [1] [4] с dp [0] [4].Значения разные, поэтому я знаю пункт 1 был выбран .Я перехожу к dp [0] [4 - вес элемента 1] => dp [0] [0].
5. dp [0] [0] - это состояние терминала, поэтому я возвращаюсь.

Результат этой операции: [1, 1, 0] где 1 означает, что item1, item2 был взят, а 0 означает, что item3 не был взят.

---

Мой вопрос:

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

Например, вместо матрицы я могу использовать 2 массива и изменить программу следующим образом:

public static void main(String[] args) {
    int[] value = {5, 4, 3};
    int[] weight = {4, 5, 2};

    int capacity = 9;

    int[] row0 = new int[capacity+1];
    int[] row1 = new int[capacity+1];
    for(int i=0; i<=3; i++) {
        for(int j=0; j<=capacity; j++) {
            if(i==0) {
                row1[j] = 0;
            } else {
                if(weight[i-1] <= j) {
                    row1[j] = Math.max(row0[j], value[i-1]+ row0[j-weight[i-1]]);
                } else {
                    row1[j] = row0[j];
                }
            }
        }
        for(int j = 0; j< row0.length; j++)
            row0[j] = row1[j];
    }

    System.out.println("optimal value is: " + row1[capacity]);

}

Если я сделаю это, то сделаю толькомаксимум две последние строки:

row0 = { 0 0 0 0 5 5 5 5 5 9 }
row1 = { 0 0 3 3 5 5 8 8 8 9 }

Как я могу отследить путь только с этой информацией?

Answer 1

Не существует хорошего решения для всех проблем DP.

Для этой задачи, например, я бы сохранял битовую маску для каждой доступной суммы, которая указывает, какие элементы вы выбрали для получения этой суммы.Это работает для ранца, потому что число элементов мало, и порядок выбора не имеет значения.

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