我一直在努力解决我在下面提到的这个问题。我有一些想法，我尝试过。我首先选择N元组的所有组合并对它们进行排序，但实现起来很难看，而且速度很慢。我认为这个问题有一种动态的编程方法。我在如何创建配置方面遇到了麻烦。在那之后，我想我知道如何解决这个问题。
问题陈述：
给定高度H（1 <= H <= 1,000,000,000），我们需要从N个元组中找到一个大于或等于H的高度序列。有几个条件： N个元组中的每一个都具有重量，高度和强度。 元组的强度表示可以在该元组之上的最大总权重。
该问题要求找到堆栈的最大安全值。安全值是可以在不超过任何较低元组强度的情况下添加的重量。如果不可能，只需打印-1。
INPUT：
第一行输入包含N和H.
接下来的N行输入描述了一个元组，给出了它的高度， 重量和力量。所有都是正整数，最多10亿。
样本输入：
4 10
9 4 1
3 3 5
5 5 10
4 4 5
样本输出：
2
好吧，既然没有其他人发布解决方案，我会抓紧抓住它。
鉴于两个元组， 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。
所以我们按顺序构建：
等等，最多 N。在构建每个列表时，我们会根据它进行修剪 规则1 以上。
规则1b： 每当更新最大强度时，应修剪所有现有列表中的强度小于或等于新最大值的元组。只要在组成新元组时遇到这些元组，就可以立即或懒惰地完成此操作。
至于算法的描述，我认为就是这样。
在实现方面，我将实际的元组存储为 std::tuple 或者a struct扭曲：对于每个产生的元组，你需要存储它所构建的主元组列表;我用了一个 std::vector<std::size_t> 为此（包含第一个列表中的主元组的索引），然后您可以使用 std::find_first_of 排除使用主要元组的组合两次，甚至更好，如果您保持列表排序， std::set_intersection。
对于每个级别的列表， std::vector 同样。
当然，实际的C ++代码是你的工作。
注意： 这里描述的算法具有非常糟糕的最坏情况复杂性特征。这种解决方案的最坏情况意味着：大 N， 大 H，小元组高度相比 H，小元组权重与其优势相比。在这种情况下，上述规则中描述的修剪都不能直到很晚才开始，直到发生这种情况，我们才会发生组合爆炸。
然而，对于我认为更有趣的情况，更高的均匀分布，高度，重量和强度（类似于给出的示例），我认为这个解决方案会很好，即使与传统的动态编程解决方案相比， ，在这种情况下，可能是整数背包解决方案的一些东西，其中一个条件被反转（没有真正想到它）。
我可能会在稍后回到这里，当时我有时间做一些实际的测量，只是出于好奇。