algorithm - 警備員と要求

Question

あなたはそれぞれコインを要求する N 人のガードを一列に並べています。彼の要求が彼に到達する前にあなたが完全に支払った金額よりも少ない場合にのみ、警備員への支払いをスキップできます. すべてのガードを越えるのに費やすコインの最小数を見つけます。

DPの問題だと思いますが、式が思いつきません。別のアプローチは、答えをバイナリ検索することですが、コインの数が可能な答えであるかどうかを確認するにはどうすればよいですか?

Answer 1

This is indeed a dynamic programming problem.

Consider the function f(i, j), which is true (one) if there is an assignment of the first i guards which give you cost j. You can arrange function f(i, j) in a table of size n x S, where S is the sum of all the guards demand.

Let us denote d_i as the demand of guard i. You can easily compute the column f(i+1) if you have f(i) by simply scanning f(i) and assigning f(i+1, j + d_i) as one if f(i + 1, j) is true and j < d_i, or f(i + 1, j) if j >= d_i.

This runs in O(nS) time and O(S) space (you only need to keep two columns per time), which is only pseudopolynomial (and quadratic-like if demands are somehow bounded and does not grow with n).

A common trick to reduce the complexity of a DP problem is to get an upper bound B on the value of the optimal solution. This way, you can prune unnecessary rows, obtaining a time complexity of O(nB) (well, even S is an upper-bound, but a very naïve one).

It turns out that, in our case, B = 2M, where M is the maximum demand of a guard. In fact, consider the function best_assignment(i), which gives you the minimum amount of coins to pass the first i guards. Let j be the guard with demand M. If best_assignment(j - 1) > M, then obviously the best assignment for the whole sequence is pay the guards for the best assignment of the first j-1 guards and skip the others, otherwise the upper-bound is given by best_assignment(j - 1) + M < 2M. But how much best_assignment(j - 1) can be in the first case? It cannot be more than 2M. This can be proven by contradiction. Let us suppose that best_assignment(j - 1) > 2M. In this assignment, the guard j-1 is paid? No, because 2M - d_{j-1} > d_{j-1}, thus it does not need to be paid. The same argument holds for j-2, j-3, ... 1, thus no guard is paid, which is absurd unless M = 0 (a very naïve case to be checked).

Since the upper-bound is proved to be 2M, the DP illustrated above with n columns and 2M rows solves the problem, with time complexity O(nM) and space complexity O(M).

Answer 2

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;
    }
}

これは、実行ごとに 2 回自分自身を呼び出す可能性があるため、O(2^N) 時間で実行されます。これは、副作用のない純粋な関数であるため、 memoizationの良い候補です。

Answer 3

これが私のアプローチです：

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) で試行されます。これが役立つことを願っています。