问题标签 [dynamic-programming]

想象一下，你和一只猫在一座高楼里。猫可以从低层窗户掉下来幸存下来，但如果从高地板上摔下来就会死。你怎么能用最少的尝试次数计算出猫可以存活的最长跌落？

显然，如果你只有一只猫，那么你只能线性搜索。先把猫从一楼扔出去。如果它幸存下来，从第二个扔掉它。最终，从 f 楼被扔下后，猫会死去。然后您就知道 f-1 层是最大安全层。

但是如果你有不止一只猫怎么办？您现在可以尝试某种对数搜索。假设该建筑有 100 层，而您有两只相同的猫。如果你把第一只猫扔出 50 层而它死了，那么你只需要线性搜索 50 层。如果您第一次尝试选择较低的楼层，您可以做得更好。假设您选择一次解决 20 个楼层的问题，而第一个致命楼层是 #50。在这种情况下，您的第一只猫将在 20 层和 40 层的飞行中幸存下来，然后从 60 层死亡。您只需分别检查 41 到 49 层。总共尝试了 12 次，这比尝试使用二元消除时需要的 50 次要好得多。

一般来说，对于有 2 只猫的 n 层建筑，最好的策略和最坏情况的复杂性是什么？n 层楼和 m 只猫呢？

假设所有的猫都是等价的：它们都会因从给定的窗户掉下来而存活或死亡。此外，每一次尝试都是独立的：如果一只猫从跌倒中幸存下来，它就完全没有受伤。

这不是家庭作业，尽管我可能曾经为学校作业解决过它。这只是今天突然出现在我脑海中的一个异想天开的问题，我不记得解决方案了。如果有人知道这个问题的名称或解决方案算法的名称，则可以加分。

一个工作的朋友向我介绍了子集和问题的一个有趣的变体：

给定一个大小为 n 的正整数集合 S，以及整数 a 和 K，是否存在一个（集合 S 的）子集 R，它恰好包含 a 个元素，其和等于 K？

他声称这可以用时间复杂度 O(nka) 来完成，我无法想出一个动态规划算法来实现这个运行时间。可以做到吗？

几天来，我一直在尝试在 Python 中实现这个算法。我不断地回到它，只是放弃并感到沮丧。我不知道发生了什么事。我没有人可以请教，也没有任何地方可以寻求帮助，所以我来到了这里。

PDF 警告：http ://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf

我不认为它解释清楚，我肯定不明白。

我对正在发生的事情的理解是这样的：

我们有一组点 (x1,y1), (x2,y2).. 我们想找到一些最适合这些数据的线。我们可以有多条直线，这些直线来自给定的 a 和 b (y = ax +b) 论坛。

现在算法从末尾开始 (?) 并假设点 p(x_i, y_i) 是线段的一部分。然后注释说最优解是 '是 {p1, . . . pi−1} 加上（最佳）线通过 {pi , . . . pn}'。这对我来说意味着，我们去点 p(x_i, y_i) 并向后走并通过其余点找到另一条线段。现在最佳解决方案是这两个线段。

然后它需要一个我无法遵循的逻辑跳转，并说“假设最后一个点 pn 是从 p_i 开始的段的一部分。如果 Opt(j) 表示前 j 个点的成本并且 e(j,k)通过点 j 到 k 的最佳直线误差 Opt(n) = e(i, n) + C + Opt(i − 1)"

然后是算法的伪代码，我不明白。我知道我们想要遍历点列表并找到最小化 OPT(n) 公式的点，但我只是不遵循它。这让我觉得自己很愚蠢。

我知道这个问题很让人头疼，而且不容易回答，但我只是在寻找一些指导来理解这个算法。我为 PDF 道歉，但我没有更简洁的方式将关键信息提供给读者。

感谢您抽出宝贵时间阅读本文，我很感激。

这是我需要解决的计算机视觉问题的简化版本。假设您有参数 n,q 并且必须计算将整数 0..(q-1) 分配给 n×n 网格的元素的方式的数量，以便对于每个分配，以下都是正确的

1. 没有两个邻居（水平或垂直）获得相同的值。
2. 位置 (i,j) 的值为 0
3. 位置 (k,l) 的值为 0

由于 (i,j,k,l) 没有给出，输出应该是上面的评估数组，对于 (i,j,k,l) 的每个有效设置一个

下面是蛮力方法。目标是获得一种适用于 q<=100 和 n<=18 的有效算法。

更新 11/11 我也在 TopCoder论坛上问过这个问题，他们的解决方案是迄今为止我见过的最有效的解决方案（根据作者的估计，n = 10，任何 q 大约需要 3 小时）

我编写了一个用于生成子集总和的程序，该程序可用于此问题，其中指出：

假设你有 3 个 1 美元硬币、2 个 2 美元硬币、3 个 5 美元硬币、1 个 10 美元硬币，有 4 种方法可以从这些硬币中获得 10 美元。如果有 n1 个 $X1 个硬币，n2 个 $X2 个硬币...... nm $Xm 个硬币，我们有多少种方法可以从这些有限数量的硬币中获得 $X？

如果我们创建一组 { X1, X1..... X1, X2, X2.......... X2, ..., ..., .... .., Xm, Xm... Xm}，然后对它运行子集求和，当然我们可以得到 $X 的结果。但我找不到使用集合 {n1, n2, n3.... nm} , {X1, X2, X3.... Xm} 的方法。一位朋友告诉我，这是背包问题的变体，但我不确定如何。

这是我写的部分代码：

如果您能详细解释一下，那对我来说会很棒。

编辑：这个问题更适合用于计算机科学的 stackexchange，但由于这是我的一个老问题，我宁愿在这里编辑它。

这个问题可以通过包含排除原则来解决，当我们将硬币值固定但每个硬币的数量随每次查询而变化时，它会派上用场。

假设，ways[v]是用$x1，$x2， .. $xm制作$v的方法，每个都可以根据需要多次使用。现在，如果我们只使用n1个$x1数字，我们必须使用至少 ( n1 + 1) 个$x1数字减去配置（这实际上是方式[ v - (n1 + 1)x1 ] ）。此外，如果我们只使用$x2的n2个数字，我们还必须减去方式[ v - (n2 + 1)x2 ]，等等。

现在，我们已经两次减去至少使用 ( n1 + 1) $x1和 ( n2 + 1) $x2的配置，因此我们需要添加方式[ v -(n1 + 1)x1 - (n2 + 1) x2 ] 等。

特别是，如果，

N = 尽可能多地使用所有硬币的一组配置，

Ai = 至少使用ni + 1 个$xi的配置集，对于 1 <= i <= m，则

我们正在寻求的结果 = | N | - | A1 | - | A2 | .. - | 上午| + | A1和A2 | + | A1和A3 | + ... - | A1和A2和A3 | ......

计算无限硬币配置数量的代码实际上更简单：

伙计们，

遇到了一个问题...发现这很有趣...正在对其进行一些修改，只是加油。

给定一组整数（范围 0-500），找出两个子集之和之间的最小差异，该差异可以通过将它们几乎均分来形成。（比如说整数的个数是 n，如果 n 是偶数，每个集合必须有 n/2 个元素，如果 n 是奇数，一个集合有 (n-1)/2 个元素，另一个有 (n+1)/2 个元素）

样品输入：1 2 3 4 5 6

最小差异 = 1（子集为 1 4 6 和 2 3 5 ）

样本输入 2：[1 1 1 1 2 2 2 2]

最小差异 = 0（子集为 1 1 2 2 和 1 1 2 2 ）

是否有针对此问题的 DP 方法。

多谢你们...

拉杰...

给定 N 个硬币的列表，它们的值 (V1, V2, ... , VN) 和总和 S。找到总和为 S 的硬币的最小数量（我们可以使用尽可能多的一种类型的硬币我们想要），或报告不可能以总和为 S 的方式选择硬币。

我试图理解动态编程，还没有弄清楚。我不明白给定的解释，所以也许你可以给我一些提示如何编程这个任务？没有代码，只是我应该从哪里开始的想法。

谢谢。

我无法弄清楚动态编程的原理，我真的很想要它。DP很强大，可以解决这样的问题：

从数字的差异中获得尽可能低的总和

那么，您能否向我推荐一些可以解释什么是动态编程的好书或文章（最好是带有真实代码的示例）？我真的想要首先简单的例子，然后我会继续。

我上周接到了这个任务，但找不到一个好的算法来解决这个问题。所以这里是描述：

您可以通过不将较大的立方体放在较小的立方体中并且如果您不将较硬的立方体放入较轻的立方体中来用构建立方体来建造一座稳定的塔。编写一个程序，为您提供具有 n 个立方体的最高塔。
输入：
在 in.txt 的第一行有立方体的数量 n (1 =< n =<1000)。下面的 n 行包含两个正整数，一个立方体的边长和重量（它们都不大于 2000），没有类似的立方体边长和重量相同
输出：
您必须将尽可能高的稳定塔的 m 数写入 out.txt。在第二行中，您必须从下到上写下塔的序数 m。塔的高度是指所有立方体的边长的数量（而不是立方体的数量）。如果有多个解决方案，您可以给出任何您想要
的输入和输出示例：
输入：
5
10 3
20 5
15 6
15 1
10 2
和输出：
3
2 1 5
这是程序的限制。时间限制：0.2 秒。内存限制：16 Mb

我希望你能帮我解决这个问题。谢谢大家的帮助

在我看来，这可能是背包问题的一个版本：我有一个不同大小的矩形列表，我想将它们放在一个字段中，而不重叠或分组相似的大小。

开始朝背包方向看是否正确？

谢谢。