7

一种算法，它将采用两个正数 N 和 K 并通过从 N 中删除 K 位将 N 转换为另一个数来计算我们可以得到的最大可能数。

例如，假设我们有 N=12345 和 K=3，所以我们可以通过从 N 中删除 3 位数字获得的最大可能数字是 45（其他转换将是 12、15、35，但 45 是最大的）。此外，您不能更改 N 中数字的顺序（因此 54 不是解决方案）。另一个例子是 N=66621542 和 K=3，所以解是 66654。

我知道这是一个与动态编程相关的问题，我不知道如何解决它。我需要解决这个问题 2 天，所以任何帮助表示赞赏。如果您不想为我解决此问题，则不必这样做，但请指出技巧或至少一些材料，我可以在其中阅读有关某些类似问题的更多信息。

先感谢您。

4

5 回答 5

6

这可以在 O(L) 中解决，其中 L = 位数。当我们可以使用堆栈来执行此操作时，为什么还要使用复杂的 DP 公式：

对于： 66621542 在堆栈上小于或等于 L - K 位时在堆栈上添加一个数字：66621。现在，从堆栈中删除小于当前读取数字的数字并将当前数字放在堆：

读取 5: 5 > 2，将 1 从堆栈中弹出。5 > 2，也弹出 2。put 5: 6665 read 4: stack is not full, put 4: 66654 read 2: 2 < 4，什么也不做。

您还需要一个条件：确保从堆栈中弹出的项目不要超过您的号码中剩余的数字，否则您的解决方案将不完整！

另一个例子：12345 L = 5, K = 3 将 L - K = 2 位放入堆栈：12

read 3, 3 > 2, pop 2, 3 > 1, pop 1, put 3. stack: 3 read 4, 4 > 3, pop 3, put 4: 4 read 5: 5 > 4, 但是我们不能pop 4，否则我们将没有足够的数字。所以推5：45。

于 2010-02-11T15:54:40.120 回答
5

好吧，要解决任何动态规划问题，您需要将其分解为重复出现的子解决方案。

假设我们将您的问题定义为 A(n, k)，它通过从 n 中删除 k 位返回可能的最大数字。

我们可以由此定义一个简单的递归算法。

使用您的示例， A(12345, 3) = max { A(2345, 2), A(1345, 2), A(1245, 2), A(1234, 2) }

更一般地说，A(n, k) = max { A(n with 1 digit removed, k - 1) }

你的基本情况是 A(n, 0) = n。

使用这种方法，您可以创建一个缓存 n 和 k 值的表。

int A(int n, int k)
{
  typedef std::pair<int, int> input;
  static std::map<input, int> cache;

  if (k == 0) return n;

  input i(n, k);
  if (cache.find(i) != cache.end())
    return cache[i];

  cache[i] = /* ... as above ... */

  return cache[i];
}

现在，这是直截了当的解决方案，但是有一个更好的解决方案可以使用非常小的一维缓存。考虑将问题改写成这样：“给定一个字符串 n 和整数 k，在长度为 k 的 n 中找到字典序上最大的子序列”。这本质上就是您的问题，解决方案要简单得多。

我们现在可以定义一个不同的函数B(i, j)，它给出长度为(i - j)的最大词典序列，仅使用n的前i位（换句话说，从前i位中删除了j位n ) 。

再次使用您的示例，我们将拥有：

B(1, 0) = 1

B(2, 0) = 12

B(3, 0) = 123

B(3, 1) = 23

B(3, 2) = 3

等等

稍微思考一下，我们可以找到递推关系：

B(i, j) = max( 10B(i-1, j) + n i , B(i-1, j-1) )

或者，如果j = i那么B(i, j) = B(i-1, j-1)

和B(0, 0) = 0

您可以以与上述非常相似的方式对其进行编码。

于 2010-02-11T15:48:35.110 回答
4

解决动态规划问题的诀窍通常是弄清楚解决方案的结构是什么样的，更具体地说，它是否表现出最佳子结构。

在这种情况下，在我看来，N=12345 和 K=3 的最佳解决方案将具有 N=12345 和 K=2 的最佳解决方案作为解决方案的一部分。如果您可以说服自己这成立，那么您应该能够递归地表达问题的解决方案。然后要么通过记忆或自下而上来实现这一点。

于 2010-02-11T14:53:50.547 回答
1

任何动态规划解决方案的两个最重要的元素是：

  1. 定义正确的子问题
  2. 定义子问题的答案和较小子问题的答案之间的递归关系
  3. 寻找基本案例，其答案不依赖于任何其他答案的最小子问题
  4. 找出您必须解决子问题的扫描顺序（这样您就永远不会使用基于未初始化数据的递归关系）

你会知道你定义了正确的子问题

  • 您需要回答的问题就是其中之一
  • 基本情况确实是微不足道的
  • 复发容易评估
  • 扫描顺序很简单

在您的情况下，指定子问题很简单。由于这可能是家庭作业，因此我将提示您，您可能希望 N 以 . 开头的位数更少。

于 2010-02-11T15:40:35.113 回答
0

这是我的想法：

考虑左边的前 k + 1 个数字。寻找最大的一个，找到它并删除左边的数字。如果存在两个相同的最大数字，则找到最左边的一个并将其左侧的数字删除。存储删除的位数（将其命名为 j ）。

将新数字作为 N 并将 k+1-j 作为 K 执行相同的操作。这样做直到 k+1 -j 等于 1（如果我没记错的话，希望它会）。

您最终得到的号码将是您正在寻找的号码。

于 2010-02-11T14:52:35.763 回答