问题标签 [dynamic-programming]

我有一个使用动态编程解决加权间隔调度问题的程序（信不信由你，它不适合家庭作业）。我已经对其进行了概要分析，而且我似乎大部分时间都在用 p(...) 填充 M。以下是功能：

我真的想不出任何优化这个的方法，根据我对这个算法的了解，这似乎是最可能占用时间的地方。但这也只是我的第二个 OCaml 程序。那么有没有办法优化呢？

我真的不知道如何使用动态编程来做到这一点：问题：我需要找到一个表的 2 个最大的非重叠正方形例如：

数字 5 和 6 分别是行数和列数，“R”表示保留，“F”表示空闲。在这种情况下，最大的正方形是

第二大（与前一个不重叠）是

到目前为止，我已将值放入二维数组，但不知道之后该怎么做。试图参考 0-1 背包和 LCS，但实际上我不知道应该在表中输入什么值。

我现在正在学习动态规划，虽然我对理论很了解，但为新问题设计 DP 算法仍然很困难。

这就是我现在真正想要的——一本书或一个网站，它提出了一个可以通过动态编程解决的问题。还有一个带有可用解释的解决方案，我想看看即使在我的头撞了几个小时后我是否也无法解决问题。是否有一些资源可以为几类算法（如图形算法、动态编程等）提供这种东西？

PS我考虑过Topcoder，但那里的解决方案并不适合学习实施有效的解决方案。

我需要在一个充满 1 和 0 的巨型文件中找到最大的 1 正方形。我知道我必须使用动态编程。我将它存储在二维数组中。找到最大正方形的算法的任何帮助都会很棒，谢谢！

示例输入：

回答：

到目前为止我的代码：

（假设值已经输入到数组中）

我该如何从那里继续？

我们有一本非常好的 GoF 书（设计模式：可重用的面向对象软件的元素）关于面向对象编程中的模式，以及网络上关于这个主题的大量文章和资源。

有没有关于函数式编程模式（最佳实践）的书籍（文章、资源）？

对于 Python 和 Ruby 等语言的动态编程？

对于 AOP？

假设您有两个长度相同的列表 L1 和 L2，N。我们将 prodSum 定义为：

假设 L1 已排序，是否有一种有效的算法可以找到 L2 的排列数，使得 prodSum(L1, L2) < 某个预先指定的值？

如果它可以简化问题，您可以假设 L1 和 L2 都是来自 [1, 2, ..., N] 的整数列表。

编辑：Managu 的回答让我相信，如果不假设 L1 和 L2 是来自 [1, 2, ..., N] 的整数列表，这是不可能的。我仍然会对假设这种约束的解决方案感兴趣。

我有一个用于 C++ 中背包的动态编程算法。当它被实现为一个函数并访问传递给它的变量时，它需要 22 秒才能在特定实例上运行。当我将它作为我的类 KnapsackInstance 的成员函数并让它使用作为该类数据成员的变量时，它开始需要 37 秒才能运行。据我所知，只有访问成员函数会通过 vtable，所以我无法解释可能发生的事情。

这是函数的代码

tbl 是 DP 表的一列。我们从第一列开始，一直到最后一列。ProfitWeights 变量是成对的向量，其中第一个元素是利润，第二个元素是权重。toret 是要返回的值。

这是原始函数的代码：-

这是在 Debian Lenny 上运行 g++-4.3.2 和 -O3 -DNDEBUG 打开的

谢谢

我最近发现了一个竞赛问题，要求您计算必须在（任何地方）插入字符串以将其变成回文的最小字符数。

例如，给定字符串：“abcbd”，我们可以通过仅插入两个字符将其变成回文：一个在“a”之后，另一个在“d”之后：“a d bcbd a ”。

这似乎是一个类似问题的概括，它要求同样的事情，除了字符只能在最后添加 - 这在 O(N) 中使用哈希表有一个非常简单的解决方案。

我一直在尝试修改Levenshtein 距离算法来解决这个问题，但没有成功。任何关于如何解决这个问题的帮助（它不一定要高效，我只是对任何 DP 解决方案感兴趣）将不胜感激。

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

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

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

先感谢您。

我想知道一般动态规划问题的目标函数是否总是可以像wiki 上的动态规划那样制定，其中目标函数是每个阶段的动作和状态项的总和？或者这只是一个特例，一般的表述是什么？

编辑：

“动态规划问题”是指可以通过动态规划技术解决的问题。这类问题具有最优问题和最优结构的性质。

但至少对我来说，有时很难识别出这样的问题，也许是因为我还没有习惯这种口头描述。当我遇到贝尔曼方程的 WIKI 页面时，我确实觉得成本函数的数学公式会有所帮助。我怀疑整体成本/收益函数总是可以表示为所有阶段的成本/收益的累积？累积可以是加法或乘法还是其他？

当我发布我的问题时，我确实意识到在更面向数学优化的某个地方讨论动态编程更合适。但是在 Stackoverflow.com 上有很多关于计算机算法的讨论。所以我也不觉得在这里问我的问题不合适。