Динамическое программирование - Алгоритм реза снизу вверх (CLRS) Решение Неправильно?

Для проблемы "резки стержня":

Дан стержень длиной n дюймов и массив цен, содержащий цены на все кусочки размером меньше n. Определите максимальное значение, которое можно получить, разрезая прут и продавая кусочки. [ ссылка]

Введение в алгоритмы (CLRS) на стр. 366 дает этот псевдокод для восходящего (динамического программирования) подхода:

1. BOTTOM-UP-CUT-ROD(p, n)              
2. let r[0 to n]be a new array .        
3. r[0] = 0                             
4. for j = 1 to n                       
5.     q = -infinity                    
6.     for i = 1 to j                   
7.         q = max(q, p[i] + r[j - i])  
8.     r[j] = q                         
9. return r[n]

Теперь у меня проблемы с пониманием логики в строке 6. Почему они делают max(q, p[i] + r[j - i]) вместо max(q, r[i] + r[j - i])? Так как это подход снизу вверх, мы будем вычислять r[1] сначала, а потом r[2], r[3]... скоро. Это означает, что при вычислении r[x] у нас гарантированно будет r [x - 1].

r[x] обозначает максимальное значение, которое мы можем получить для стержня длины x (после разрезания его для максимизации прибыли), тогда как p[x] обозначает цену одного куска стержня длины x. Строки 3 - 8 вычисляют значение r[j] для j = 1 до n и строки 5 - 6 вычисляют максимальную цену, за которую мы можем продать стержень длины j, рассматривая все возможные сокращения. Итак, как же имеет смысл использовать p[i] вместо r[i] в ​​строке 6. Если мы пытаемся найти максимальную цену на стержень после того, как мы разрезаем его на длину = i, разве мы не должны добавлять цены? из r[i] и r[j - 1]?

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

class Solution {
    private static int cost(int[] prices, int n) {
        if (n == 0) {
            return 0;
        }

        int[] maxPrice = new int[n];

        for (int i = 0; i < n; i++) {
            maxPrice[i] = -1;
        }

        for (int i = 1; i <= n; i++) {
            int q = Integer.MIN_VALUE;

            if (i <= prices.length) {
                q = prices[i - 1];
            }

            for (int j = i - 1; j >= (n / 2); j--) {
                q = Math.max(q, maxPrice[j - 1] + maxPrice[i - j - 1]);
            }

            maxPrice[i - 1] = q;
        }

        return maxPrice[n - 1];
    }


    public static void main(String[] args) {
       int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};

        System.out.println(cost(prices, 8));
    }
}
Источник

2 ответа

Решение

Они должны быть эквивалентны.

Интуиция, лежащая в основе подхода CLRS, состоит в том, что они пытаются найти единственный "последний разрез", предполагая, что последний кусок стержня имеет длину i и, таким образом, имеет значение именно p[i], В этой формулировке "последний кусок" длины i дальше не режется, а остаток длины j-i является.

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

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

Источник

Я думаю, что оба подхода верны.

прежде чем мы докажем, что оба они верны, давайте определим, что именно делает каждый подход

p[i] + r[j - i] даст вам максимальное значение, которое вы можете получить из стержня длины j, а часть имеет размер "i"(не может разделить эту часть дальше)

r [i] + r [ji] даст вам максимальное значение, которое вы можете получить от стержня длины i, а первый разрез был сделан на длине "i"(можно разделить обе части дальше)

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

и так как k равно 0

и во втором подходе вы можете найти тот же результат с r [k] + r[Xk], так как мы знаем, что r [k] будет>= p[k]

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

Но я думаю, что в вашем коде есть ошибка во внутреннем цикле for, это должно быть j >= (i / 2) вместо j >= (n / 2)

Источник
Другие вопросы по тегам