Pra*_*Som 11 c++ algorithm dynamic-programming adhoc
我一直在努力解决我在下面提到的这个问题.我有一些想法,我尝试过.我首先选择了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,扭曲:对于每个产生的元组,你需要存储它所构建的主元组列表; 我会使用a std::vector<std::size_t>(包含第一个列表中主要元组的索引),因为您可以使用它std::find_first_of来排除使用主要元组的组合两次,甚至更好,如果您保持列表排序,std::set_intersection.
对于每个级别的列表std::vector.
实际的C++代码当然是你的工作.
注意:此处描述的算法具有非常糟糕的最坏情况复杂性特征.这种解决方案的最坏情况意味着:与其强度相比,小元组权重大N,大H,小元组高度H.在这种情况下,上述规则中描述的修剪都不能直到很晚才开始,直到发生这种情况,我们才会发生组合爆炸.
然而,对于我所看到的更有"有趣"的情况,具有更均匀的高度,重量和强度分布(类似于给出的示例),我认为这个解决方案会很好,甚至与传统的动态编程解决方案相比,在这种情况下,可能是整数背包解决方案的一些东西,其中一个条件被反转(没有真正想到它).
我可能会在稍后回到这里,当时我有时间做一些实际的测量,只是出于好奇.