Охранники и спрос

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

Я думаю, что это проблема DP, но не могу придумать формулу. Другим подходом был бы бинарный поиск ответа, но как я могу проверить, является ли количество монет возможным ответом?

3 7
algorithm dynamic-programming

3 ответа:

Это действительно проблема динамического программирования.

Рассмотрим функцию f(i, j), которая является true (одна), если есть назначение первых i охранников, которые дают вам стоимость j. Вы можете расположить функцию f(i, j) в таблице размера n x S, где S - сумма всех требований охранников.

Обозначим d_i как требование охраны i. Вы можете легко вычислить столбец f(i+1), Если у вас есть f(i), просто сканируя f(i) и назначая f(i+1, j + d_i) как один, если f(i + 1, j) истинно и j < d_i, или f(i + 1, j), Если j >= d_i.

Это работает в O(nS) времени и O(S) пространстве (вам нужно только сохранить два столбца за время), которое является только псевдополиномиальным (и квадратичным, если требования каким-то образом ограничены и не растут с n).

Распространенный трюк для уменьшения сложности задачи DP состоит в том, чтобы получить верхнюю границу B значения оптимального решения. Таким образом, вы можете обрезать ненужные строки, получив временную сложность O(nB) (ну, даже S является верхний предел, но очень наивный).

Получается, что в нашем случае B = 2M, где M - максимальная потребность охранника. В самом деле, рассмотрим функцию best_assignment(i), которая дает вам минимальное количество монет для прохождения первой i Стражи. Пусть j будет стражем с требованием M. Если best_assignment(j - 1) > M, то очевидно, что лучшее назначение для всей последовательности-заплатить охранникам за лучшее назначение первых j-1 охранников и пропустить остальных, в противном случае верхняя граница задается best_assignment(j - 1) + M < 2M. Но сколько может быть в первом случае? Это не может быть больше, чем 2M. Это может быть доказано противоречием. Предположим, что best_assignment(j - 1) > 2M. В этом задании охранник j-1 оплачивается? Нет, потому что 2M - d_{j-1} > d_{j-1}, таким образом, он не должен быть оплачен. Тот же аргумент справедлив и для j-2, j-3, ... Таким образом, охрана не оплачивается, что абсурдно, если только M = 0 (очень наивный случай, который нужно проверить).

Поскольку верхняя граница доказана как 2M, DP иллюстрируется выше столбцами n и 2M rows решает проблему, с временной сложностью O(nM) и пространственной сложностью O(M).

9
function crossCost(amtPaidAlready, curIdx, demands){
    //base case: we are at the end of the line
    if (curIdx >= demands.size()){
        return amtPaidAlready;
    }

    costIfWePay = crossCost(amtPaidAlready + demands[curIdx], curIdx+1, demands);
    //can we skip paying the guard?
    if (demands[curIdx] < amtPaidAlready){
        costIfWeDontPay = crossCost(amtPaidAlready, curIdx+1, demands);
        return min(costIfWePay, costIfWeDontPay);
    }
    //can't skip paying
    else{
        return costIfWePay;
    }
}

Это выполняется за O (2^N) время, потому что он может вызвать себя дважды за выполнение. Это хороший кандидат для запоминания , потому что это чистая функция без побочных эффектов.

2

Вот мой подход: 

int guards[N];
int minSpent;

void func(int pos, int current_spent){
    if(pos > N)
        return;
    if(pos == N && current_spent < minSpent){
        minSpent = current_spent;
        return;
    }

    if(guards[pos] < current_spent)      // If current guard can be skipped
        func(pos+1,current_spent);       // just skip it to the next guard
    func(pos+1,current_spent+guards[pos]);   // In either cases try taking the current guard
}

Используется следующим образом: 

minSpent = MAX_NUM; 
func(1,guards[0]);

Это будет пробовать все возможности его O (2^N), надеюсь, это поможет.

0