[Solved]: Find subsequence of maximal length simultaneously satisfying two ordering constraints

Problem Detail: 

We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to arrange these fruits in such a way that the sorted list contains prices in ascending order and vitamin contents in descending order.

Example 1: $N = 4$ and $F = \{(2, 8), (5, 11), (7, 9), (10, 2)\}$.

If we arrange the list such that all price are in ascending order and vitamin contents in descending order, then the valid lists are the following:

• $[(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)]$

From the above lists, I want to choose the list of maximal size. If more than one list has maximal size, we should choose the list of maximal size whose sum of prices is least. The list which should be chosen in the above example is $\{(5, 11), (7, 9), (10, 2)\}$.

Example 2: $N = 10$ and $$F = \{(99,10),(12,23),(34,4),(10,5),(87,11),(19,10), \\(90,18), (43,90),(13,100),(78,65)\}$$

The answer to this example instance is $[(13,100),(43,90),(78,65),(87,11),(99,10)]$.

Until now, this is what I have been doing:

1. Sort the original list in ascending order of price;
2. Find all subsequences of the sorted list;
3. Check whether the subsequence is valid, and compare all valid subsequences.

However, this takes exponential time; how can I solve this problem more efficiently?

Asked By : Jack

Answered By : Tom van der Zanden

A dynamic programming solution would work here, if the vitamin contents come from a finite set (for instance, bounded integers). First, sort the fruits on price ascending and in the cases were two or more fruit have the same price, sort them on vitamin content (descending). Now, define $M[f, v]$ to be the maximal number of fruits in a sublist, containing only the last $f$ fruits (of the sorted list), having a vitamin content of at most $v$. $M[0, *] = 0$ and $$M[f, v] = \begin{cases} \mathrm{max} \{M[f-1, v], 1 + M[f-1, V_f]\} & \text{if \(V_f <= v\)} \\ M[f-1, v] & \text{otherwise} \\ \end{cases}$$ Using dynamic programming gives you a solution that runs in $O(\text{number of fruit} \times \text{possible vitamin values})$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1287

3.2K people like this

 Download Related Notes/Documents