Минимальная стоимость корректировки - PullRequest
Новая
       15

Минимальная стоимость корректировки

0 голосов
/ 25 октября 2019

Я пытаюсь решить этот вопрос:

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

Если массив до корректировки равен A, массив после корректировки равен B, вы должны минимизировать сумму `|A [i] -B [i] |. Можно предположить, что каждое число в массиве является положительным целым числом и не превышает 100.

`

Я вижу решение ДП, но я не совсем понимаю уравнение повторения. 

public static int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    // write your code here
    if (A == null || A.size() == 0) {
        return 0;
    }

    // D[i][v]: 把index = i的值修改为v，所需要的最小花费
    int[][] D = new int[A.size()][101];

    int size = A.size();

    for (int i = 0; i < size; i++) {
        for (int j = 1; j <= 100; j++) {
            D[i][j] = Integer.MAX_VALUE;
            if (i == 0) {
                // The first element.
                D[i][j] = Math.abs(j - A.get(i));
            } else {
                for (int k = 1; k <= 100; k++) {
                    // 不符合条件 
                    if (Math.abs(j - k) > target) {
                        continue;
                    }

                    int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
                    D[i][j] = Math.min(D[i][j], dif);
                }
            }
        }
    }

    int ret = Integer.MAX_VALUE;
    for (int i = 1; i <= 100; i++) {
        ret = Math.min(ret, D[size - 1][i]);
    }

    return ret;
}

Может ли кто-нибудь мне это объяснить?

1 Ответ

1 голос
/ 26 октября 2019

Вам необходимо минимизировать стоимость уравнивания, то есть значение, которое вы увеличиваете / уменьшаете для каждого элемента, так что разница между всеми соседними элементами меньше или равна target. Решение dp состоит в том, чтобы попробовать все возможные значения и минимизировать стоимость действительных значений (когда abs(A[i]-A[i-1]) <= target)

Прежде всего необходимо заполнить стоимость настройки первого элемента на 1-100, что делается здесь: 

 for (int i = 0; i < size; i++) {
        for (int j = 1; j <= 100; j++) {
            D[i][j] = Integer.MAX_VALUE; // fill with MAX_VALUE because we want to minimize
            if (i == 0) {
                // for the first element we just set the cost of adjusting A[i] to j
                D[i][j] = Math.abs(j - A.get(i));
            }

Теперь у вас есть D[0][j] в качестве стоимости для настройки первого элемента на j. Затем для каждого другого элемента вы повторяете цикл (от k = 1 до k = 100) для других элементов и пытаетесь изменить A[i] на j. Затем вы проверяете, действительно ли abs(k-j) (меньше или равно target), затем вы можете настроить A[i] на j и A[i-1] на k, чтобы свести к минимуму D[i][j].

Здесь D[i][j] означает стоимость изменения A[i] до j, а D[i-1][k] - это стоимость изменения A[i-1] до k. поэтому для каждых k и j, если они действительны (abs(k-j)<=target), вы складываете их вместе и минимизируете значение, сохраненное в D[i][j], чтобы вы могли использовать его для следующего элемента, что делается здесь: 

else {
    for (int k = 1; k <= 100; k++) {
        // if abs(j-k) > target then changing A[i] to j isn't valid (when A[i-1] is k)
        if (Math.abs(j - k) > target) {
            continue;
        }
        // otherwise, calculate the the cost of changing A[i] to j and add to it the cost of changing A[i-1] to k
        int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
        // minimize D[i][j]
        D[i][j] = Math.min(D[i][j], dif);
     }
}

В конце вам нужно зациклить от 1 до 100 в последнем элементе и проверить, какое минимальное значение для всех, что делается здесь: 

int ret = Integer.MAX_VALUE;
for (int i = 1; i <= 100; i++) {
    ret = Math.min(ret, D[size - 1][i]);
}

Я думаю, если выразделите код инициализации и код вычисления DP, это будет легче понять, например: 

// fill the initial values
for (int i = 0; i < size; ++i) {
    for (int j = 1; j <= 100; ++j) {
        // on the first element just save the cost of changing
        // A[i] to j
        if (i == 0) {
            DP[i][j] = abs(j-A.get(i));
        } else {
            // otherwise intialize with MAX_VALUE
            D[i][j] = Integer.MAX_VALUE;        
        }

    }
}
for (int i = 1; i < size; i++) {
    for (int j = 1; j <= 100; j++) {
        for (int k = 1; k <= 100; k++) {
            // if abs(j-k) isn't valid skip it
            if (Math.abs(j - k) > target) {
                continue;
            }
            // if it is valid, calculate the cost of changing A[i] to j
            // and add it to the cost of changing A[i-1] to k then minimize
            // over all values of j and k
            int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
            D[i][j] = Math.min(D[i][j], dif);
        }
    }
}

// calculate the minimum cost at the end
int ret = Integer.MAX_VALUE;
for (int i = 1; i <= 100; i++) {
    ret = Math.min(ret, D[size - 1][i]);
}
...