动态编程:网球，储物柜和钥匙 [英] Dynamic Programming: Tennis Balls, Lockers, and Keys

问题描述

我在寻找问题的最佳动态编程解决方案时遇到困难，非常感谢您的帮助.最优解为O(T ^ 2 + M);我只能找到O(NM ^ 2)的解决方案. 问题是:

有N个标有1,2 ... N的储物柜.每个储物柜均已锁定，但可以使用其唯一钥匙打开.每个储物柜的钥匙副本都位于其相邻的储物柜中.即将储物柜i的钥匙的副本放置在储物柜i + 1和i-1中(储物柜1的钥匙仅在储物柜2中，储物柜N的钥匙仅在储物柜N-1中)

T个网球位于T个不同的储物柜中(您知道它们位于哪个储物柜中).为您提供了M个储物柜的钥匙，您的目标是通过打开最少数量的储物柜来收集所有网球.

我唯一给出的提示是: 提示:您可以有效地确定ith和jth储物柜之间是否至少存在一个网球吗?

解决方案

首先将一个虚拟单元格放在 N + 1 上，没有钥匙，没有钥匙.

现在从第二个键开始，一直进行到最后一个键(您应该注意，这是一个虚拟键).

在每次迭代中，针对两种情况，计算当前键左侧(含)的网球的最佳解.使用当前密钥，并且b.当前密钥未使用.最佳解决方案还应该记录实际使用的最右边的密钥.

如果不使用当前关键点，则使用前两个最佳解决方案来更新成本，使用实际上用于覆盖当前关键点(包括该关键点)左侧的球的最右边的关键点.如果使用了当前键，则对于当前键左侧(包括该键)左侧的每个球，计算从该键还是从先前使用的键打开是否值得(取决于键之间的中点)./p>

整体解决方案是位于 N + 1 虚拟单元格中的解决方案，并且不使用其中的密钥.

I am having trouble finding the Optimal Dynamic Programming solution to a problem and would greatly appreciate any help. The optimal solution is O(T^2+M); I can only find a solution which is O(NM^2). The problem is:

There are N lockers that are labeled 1,2...N. Each locker is locked, but can be opened using it's unique key. Copies of the key to each locker are in its adjacent lockers; i.e. a copy of the key to locker i is placed in locker i+1 and i-1 (the key to locker 1 is only in locker 2 and the key to locker N is only in locker N-1)

T tennis balls are inside T distinct lockers (and you know which lockers they are in). You are given keys to M of the lockers and your goal is to collect all of the tennis balls by opening the least number of lockers.

My only hint given is: Hint: Can you efficiently decide whether there exist at least one tennis ball between the ith and jth locker?

解决方案

First place a dummy cell at N + 1 with a key and no tennis ball.

Now start at the second key, and proceed until the last key (which, you should note, is a dummy key).

At each iteration, calculate the optimal solution to the tennis balls to the left of the current key (inclusive) for two cases: a. the current key is used, and b. the current key is not used. The optimal solution should also record the rightmost key actually used.

If the current key is not used, then use the previous best two solutions to update the cost, using the rightmost key actually used for covering the balls to the left of the current key (inclusive). If the current key is used, then for each of the balls to the left of the current key (inclusive), calculate whether it pays to open from this key or the previously used key (it depends on the midpoint between the keys).

The overall solution is the one that is at the dummy N + 1 cell, and doesn't use the key in it.

这篇关于动态编程:网球，储物柜和钥匙的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！