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位中删除了jn ) 。

再次使用您的示例,我们将拥有:

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 回答