7

你有 N 个守卫排成一列，每个守卫都需要硬币。只有当他的要求低于你在到达他之前支付的全部金额时，你才可以跳过支付警卫。找出你花费最少的硬币来越过所有守卫。

我认为这是一个 DP 问题，但无法提出公式。另一种方法是对答案进行二分搜索，但我如何验证是否有多个硬币是可能的答案？

4

3 回答 3

9

这确实是一个动态规划问题。

考虑函数，如果有分配给你 cost 的第一个守卫f(i, j)，它是（一个） 。您可以在 size 的表中安排功能，其中是所有警卫需求的总和。trueijf(i, j)n x SS

让我们表示d_i为警卫的需求i。f(i+1)如果您有，您可以轻松地计算列f(i)，只需扫描f(i)并指定f(i+1, j + d_i)为一个 iff(i + 1, j)为 true 和j < d_i，或f(i + 1, j)if j >= d_i。

这在O(nS)时间和O(S)空间上运行（您每次只需要保留两列），这只是伪多项式（如果需求以某种方式有界并且不随 增长，则类似于二次n）。

B降低 DP 问题复杂性的一个常见技巧是获得最优解值的上限。这样，您可以修剪不必要的行，获得时间复杂度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。best_assignment(j - 1)但是在第一种情况下可以有多少？不能超过2M。这可以用反证法来证明。让我们假设best_assignment(j - 1) > 2M。在这个任务中，守卫j-1是有报酬的吗？不，因为2M - d_{j-1} > d_{j-1}，因此不需要支付。同样的论点适用于j-2,j-3, ... 1，因此没有支付警卫，这是荒谬的，除非M = 0（一个非常幼稚的情况需要检查）。

由于上界被证明是，所以上面用列和行2M说明的 DP解决了这个问题，时间复杂度和空间复杂度为。n2MO(nM)O(M)

于 2013-02-04T13:26:42.450 回答
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;
    }
}

这在 O(2^N) 时间内运行，因为每次执行它可能会调用自己两次。它是memoization的一个很好的候选者，因为它是一个没有副作用的纯函数。

于 2013-02-04T13:03:30.900 回答
0

这是我的方法：

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) 的所有可能性，希望这会有所帮助。

于 2013-02-04T13:08:22.510 回答