Finding and proving a greedy algorithm to maximize total energy

algorithmscomputational complexitycomputer sciencediscrete mathematicsfunctions

Find a function $f:\mathbb{R}^2\to \mathbb{Z}$ that satisfies the following properties, or show that no such function exists:

  • $f$ is increasing with respect to its first coordinate (i.e. $f(x, a) \leq f(y,a)$ for $x\leq y$)
  • $f$ is decreasing with respect to its second coordinate (i.e. $f(a, x) \leq f(a,y)$ for $x\ge y$).
  • $f$ can be used to solve the problem below as follows:

sort the $n$ pairs $(e[i], d[i])$ in decreasing order according to the value of $f$. When going through the new pairs in the sorted order, suppose you reach fruit $i$. Add $e[i]$ to the maximum if fruit $i$ is not yet expired.

Or find an alternative way to come up with a greedy algorithm to solve the problem below.

There are $n$ fruits, and each has an associated energy level, stored in the array e[1…n]. Also, each fruit has an expiry date, stored in the array d[1…n] (d[i] is the number of days from today fruit i expires). Both e[1…n] and d[1…n] only store positive values. A person wishes to maximize the total energy of the fruits they can take subject to the constraint that they take at most one fruit per day.

How would one design and prove a greedy algorithm for this problem?

I can't seem to find a correct greedy algorithm for this problem. I initially thought of repeatedly choosing the fruit with the highest ratio of energy to days until expiry, but there are counterexamples for this. For instance, consider the fruits satisfying $d = [3,1,2,4], e = [1,11,10,20]$. The greedy algorithm would choose fruits $2$ (ratio 11/1), 3 (ratio 10/1), 4 (ratio 20/1), giving an energy value of 41, which is smaller than the optimum of 42.

Also, I was wondering if there was an $o(n^2)$ greedy algorithm? If not, a dynamic programming algorithm running in $o(n^2)$ time is also fine.

Also, is it true that if any d[i] > n, then any optimal solution must select fruit $i$?

Best Answer

My algorithm is same as this answer but using Disjoint-set data structure. In this solution, i am assuming that the range of dates is O(n).

Let each date from minimum date to maximum expiry date (including both) be a set with single element date. The representative of these sets is always empty and can be used to place the fruit. Let us also create a sentinel set before the minimum date in which fruit cannot be placed.

Greedy solution

  1. At each stage, select the maximum energy fruit $i$. Find the representative of the set containing $d[i]$.
  2. If the representative is the sentinel, remove the fruit.
  3. If the representative is not a sentinel but the date $d'$, then place the fruit in the date $d'$ and combine the sets containing $d'$ and $d'-1$.

Extra

There is a mathematical structure called Weighted Matroid which has nice properties that helps us in solving greedy algorithms. This question can be reframed into a weighted matroid with independent set - set of fruits that follows the deadline constraint and weight - energy. For more details, you can look at the book "Introduction to Algorithms", chapter 16 Greedy algorithms, section Matroids.

Edit

To answer your second question

Also, is it true that if any d[i] > n, then any optimal solution must select fruit $i$?

Let $i$ be a fruit with $d[i] \ge n$. Let us assume that there exists an optimal configuration $C$ without fruit $i$. Hence $C$ has atmost $n-1$ fruits in it which implies $C$ has atmost $n-1$ fruits in the first $n$ days. So there exists an extra space within $d[i]$ where $i$ can be placed in $C$ and make it more optimal which is a contradiction since $C$ was assumed to be optimal. Hence any configuration must have fruit $i$ if $d[i] \ge n$.

Also, I don't have to assume that range of dates is O(n). The range of dates can be exactly $n$ because by the above statement, if $d[i]$ for any fruit $i$ is greater than $n$, we can set it back to $n$ and this won't change the solution space.

Related Question