好的,既然没有其他人发布解决方案,我来试试。
给定两个元组,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进行修剪。
< p >
规则1b:每当最大强度更新时,所有现有列表都应修剪掉强度小于或等于新最大值的元组。这可以立即完成,也可以在将这些元组作为组成新元组的一部分时进行惰性处理。
就算法描述而言,我认为就是这样。
在实现方面,我会将实际元组存储为std::tuple
或struct
,并加以改进:对于每个生成的元组,您需要存储它是由哪些原始元组构建而成的列表;我会使用std::vector<std::size_t>
(其中包含第一个列表中主元组的索引)来实现,因为您可以使用std::find_first_of
来排除使用主元组两次的组合,甚至更好的方法是,如果保持列表排序,则可以使用std::set_intersection
。
对于每个级别的列表,也使用std::vector
。
实际的C++代码当然是你的工作。
注意: 这里描述的算法具有非常糟糕的最坏复杂度特性。对于这个解决方案来说,最坏情况意味着:大量的
N
,大量的
H
,与
H
相比,元组高度较小,元组重量较小。在这种情况下,除非很晚才能出现上述规则中所描述的任何修剪操作,否则我们会出现组合爆炸。
然而,在我看来,对于更均匀分布高度、重量和强度的更“有趣”的情况(类似于给定的示例),我认为这个解决方案表现得相当不错,甚至与经典的动态规划解决方案相比也不遑多让,这种情况下,后者可能是类似于整数背包解决方案的一个条件被反转(还没有真正思考过)。
以后如果有时间做一些实际测量,只是出于好奇,我可能会回到这个问题。
H
扮演什么角色? 你所说的堆栈是什么? 您可以尝试为示例输入解释这些内容,并展示示例输出是正确答案。 - PradhanH
”时,H
是元组列表的最大高度吗? - Rerito