找到同时满足两个排序约束的最大长度的子序列

Question

给我们一个$ f = {f_1，f_2，f_3，…，f_n } $ $ n $ fruits的$。每个水果都有价格$ p_i $和维生素含量$ v_i $;我们将水果$ f_i $与订购对$（p_i，v_i）$相关联。现在，我们必须以这样的方式安排这些水果，以使分类的列表包含上升顺序和维生素内容的价格下降顺序。

示例1: ：$ n = 4 $和$ f = {（2，8），（5，11），（7，9），（10，2）} $。

如果我们安排清单，以使所有价格按升序和维生素内容按降序订购，则有效列表如下：

• $[(2, 8)]$
• $[(5, 11)]$
• $[(7, 9)]$
• $[(10, 2)]$
• $[(2, 8), (10, 2)]$
• $[(5, 11), (7, 9)]$
• $[(5, 11), (10, 2)]$
• $[(7, 9), (10, 2)]$
• $[(5, 11), (7, 9), (10, 2)]$

从上面的列表中，我想选择最大尺寸的列表。如果多个列表具有最大尺寸，我们应该选择最小价格之和最少的最大尺寸列表。上面示例中应选择的列表为$ {（5，11），（7，9），（10，2）} $。

示例2: ：$ n = 10 $和$$ f = {（99,10），（12,23），（34,4），（10,5），（87,11），（19,10）， （90,18），（43,90），（13,100），（78,65）} $$

此示例实例的答案是$ [（13,100），（43,90），（78,65），（87,11），（99,10）] $。

到目前为止，这就是我一直在做的事情：

1. 按价格上升顺序对原始列表进行排序；
2. 找到排序列表的所有子序列；
3. 检查子序列是否有效，并比较所有有效的子序列。

但是，这需要指数时间。如何更有效地解决这个问题？

Answer 1

如果维生素含量来自有限集（例如，有限整数），则在这里可以使用动态编程解决方案。首先，按价格上升的果实排序，在这种情况下，有两个或更多的水果具有相同的价格，对维生素含量（下降）进行排序。现在，将$ m [f，v] $定义为冠军中的最大水果数量，仅包含最后一个$ f $ fulit（排序列表的），最多只有$ v $的维生素含量。 $ m [0， *] = 0 $和$$ m [f，v] = begin {cases} mathrm {max} {m [f-1，v]，1 + m [f-1，v_f，v_f ] }＆ text {if （v_f <= v ）} m [f-1，v]＆ text {否则} end end {cases} $$使用动态编程为您提供一个解决方案，该解决方案是一个解决方案以$ o（ text {水果} times text {可能的维生素值}）$运行。