В чем преимущество инициализации int maxValue = Integer.MIN_VALUE в Dynami c Programming? - PullRequest
Новая
       30

В чем преимущество инициализации int maxValue = Integer.MIN_VALUE в Dynami c Programming?

0 голосов
/ 12 июля 2020

Чтобы точно задать вам этот вопрос, в чем преимущество инициализации int max_val = Integer.MIN_VALUE над int max_val = price [i-1]?

Это может показаться тривиальной проблемой DP. Но мне нужна твоя помощь. Общие проблемы DP начинаются с инициализации max_val как Integer.MIN_VALUE. Я знаю, что это стандартный способ.

Но я понял, что установка max_val как price [i-1] не является неправильной.

например, я получил 22 с arr = {1 5 8 9 10 17 17 20} и cutRod (arr, 8).

Я получил 24 с arr = {3 5 8 9 10 17 17 20} и cutRod (arr, 8). 

public class RodCutting {
    public static void main(String[] args) {
        int[] arr = new int[] {2, 5, 13, 19, 20};
        int size = arr.length;
        int result = cutRod(arr, size);
        System.out.println("Maximum Obtainable Value is " + result);
    }

    private static int cutRod(int[] price, int n) {
        int val[] = new int[n+1];
        val[0] = 0;

        for (int i = 1; i <= n; i++) {
            int max_val = price[i-1]; // previously, int max_val = Integer.MIN_VALUE;
            for (int j = 0; j < i; j++) 
                max_val = Math.max(max_val,  val[j+1]+ val[i - j - 1]); 
                // previously, max_val = Math.max(max_val, price[j] + val[i - j - 1]);

            val[i] = max_val;
        }
        return val[n];
    }
}

Заранее спасибо.

1 Ответ

1 голос
/ 12 июля 2020

В общем смысле, нет сильного «преимущества» инициализации локальной переменной Integer.MIN_VALUE ... по сравнению с любым другим значением, которое гарантированно будет меньше или равно максимальному, который вы вычисляете. 1003 * В данном случае эта настройка явно не влияет на вычислительную сложность. Еще нужно выполнить внутренние l oop j - i раз. Это может повлиять на ветвление внутри вызова Math.max, но я сомневаюсь, что разница в производительности будет значительной ... В любом случае, единственный способ убедиться в этом - это тщательное тестирование с большим набором репрезентативных входных данных. И это даст вам ответ только на эту конкретную проблему.

Однако вы знаете, что Integer.MIN_VALUE должно быть меньше или равно этому фактическому максимуму. Таким образом, использование этого значения означает, что для подтверждения правильности требуется на одну вещь меньше. (Или, другими словами, это может упростить понимание вашего кода.)

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

А если это слишком много ... прислушайтесь к совету Кнута по преждевременной оптимизации.

...