c++ - 使用动态规划创建最大配置

Question

我一直在努力解决我在下面提出的这个问题。我有一些我尝试过的想法。我首先选择了 N 个元组的所有组合并对它们进行排序，但实现起来很丑陋，而且速度很慢。我认为有一个动态编程方法可以解决这个问题。我在如何创建配置方面遇到了问题。在那之后，我想我知道如何解决问题了。

问题陈述:

给定高度 H (1 <= H <= 1,000,000,000)，我们需要从 N 个元组中找到一个大于或等于 H 的高度序列。有几个条件:
N 个元组中的每一个都具有重量、高度和强度。
元组的强度表示可以在该元组之上的最大总重量。

该问题要求找到堆栈的最大安全值。安全值是在不超过任何下元组强度的情况下可以添加的重量。如果不可能，只需打印出-1。

输入:

输入的第一行包含 N 和 H。

接下来的 N 行输入每行描述一个元组，给出它的高度，
重量和强度。都是最多 10 亿的正整数。

样本输入:

4 10

9 4 1

3 3 5

5 5 10

4 4 5

sample 输出:

2

Answer 1

好吧，由于没有其他人发布了解决方案，我会尝试一下。

给定两个元组，t1 = (h1, w1, s1)和 t2 = (h2, w2, s2) ，我们可以将它们组合为[t1 over t2]或 [t2 over t1] .在每种情况下，我们都可以将结果视为另一个元组；例如，

t3 = [t1 over t2] = (h1 + h2, w1 + w2, min(s1, s2 - w1))

(生成的元组的强度不能高于组件元组的两个强度中的任何一个，并且底部元组的强度会因其顶部元组的重量而降低；生成的强度可以为负)。

无论组合顺序如何，生成的元组的高度和重量都是相同的；然而，所得强度可能因订单而异。我们对最大强度的元组感兴趣，所以我们取两个可能值中的最大值。鉴于上述情况，让我们将组合定义为

t1 + t2 = (h1 + h2, w1 + w2, max(min(s1, s2 - w1), min(s2, s1 - w2)))

结果元组又可以与其他元组组合，依此类推。

我们需要的是从所有得到的高度至少为 H 的元组中找到最大强度。 ，因为问题中要求的最大安全值实际上是结果元组的强度。

因此，我们可以将起始最大强度设置为 -1 ，开始组合元组，每当我们找到一个高度 H或者更多，如果元组的强度更大，则更新当前的最大强度。

规则 1:生成的元组的强度不能高于组成元组的两个强度中的任何一个，因此，在组合元组时，每当我们发现强度小于或等于当前最大值时，我们可以丢弃它，因为没有元组其中它将是一个组件的强度可以高于当前的最大值。

规则 1a:我们甚至可以丢弃用于更新当前最大强度的元组，因为问题不要求我们提供元组本身，只要求提供最大值，并且该元组不会在任何其他情况下生成更好的最大值组合。

规则 2:现在，让我们自上而下地看一下。任意堆栈 n = 2k元组可以看成是由两个元组组成，每个元组由一堆 k组成元组；为 n = 2k + 1 ，两个堆栈的大小为 k和 k + 1 .

所以我们按顺序构建:

初始元组列表；

由两个堆栈产生的元组列表；

由三个堆栈产生的元组列表，元组通过从列表 [1] 中获取一个元组和从列表 [2] 中获取一个元组(所有组合，不包括两次使用主元组的组合)；

由四个堆栈产生的元组列表，其中的元组由两个元组组成，均来自列表 [2](同样，所有组合，不包括两次使用主元组的组合)；

依此类推，直至 N .在构建每个列表时，我们根据上面的规则 1 对其进行修剪。

规则 1b:每当最大强度更新时，所有现有列表都应从强度小于或等于新最大值的元组中修剪掉。每当遇到这些元组作为组成新元组的一部分时，这可以立即或懒惰地完成。

就算法的描述而言，我认为就是这样。

在实现方面，我将实际的元组存储为 std::tuple或 struct ，有一点:对于每个生成的元组，您需要存储构建它的主要元组列表；我会使用 std::vector<std::size_t>为此(包含来自第一个列表的主元组的索引)，然后您可以使用 std::find_first_of 排除两次使用主元组的组合，甚至更好，如果您保持列表排序， std::set_intersection .

对于每个级别的列表， std::vector以及。

当然，实际的 C++ 代码是您的工作。

注:这里描述的算法具有非常糟糕的最坏情况复杂性特征。此解决方案的最坏情况意味着:大 N , 大 H ，与 H 相比，元组高度较小，与它们的优势相比，小元组权重。在这种情况下，上述规则中描述的修剪都不能在很晚之前开始，直到发生组合爆炸。

然而，对于我认为更“有趣”的情况，高度、体重和力量的分布更均匀(类似于给出的例子)，我认为这个解决方案会很好，即使与经典的动态规划解决方案相比， ，在这种情况下，可能与整数背包解决方案类似，其中一个条件倒置(还没有真正考虑过)。

稍后我可能会回到这个话题，当我有时间做一些实际测量时，只是出于好奇。