Sell rotting apples in time

Question

I am stuck regarding the following question. Do you have an idea? Of course, brute-forcing all permutations solves the problem. However, is there another approach?

Suppose you sell apples and each apple has an associated "time to rot" until it cannot be sold anymore.

Suppose also that all apples have a separate price dependent on their aesthetics. The price is constant until the apple has rotten, then it becomes zero.

Selling an apple takes some constant time, therefore you cannot sell them all but only the first k apples.

In which order should you sell your slowly rotting apples in order to maximize your outcome?

Do you have any hints which type of literature could help here? Like operations research or queueing theory?

Answer 1

I think a simple dynamic programming will work:

T(i, j) = 0 #if i>|apples|
T(i, j) = T(i+1, j) #if j/k >= rot(i)
T(i, j) = max(value(i) + T(i+1, j+1), T(i+1, j)) #if j/k < rot(i)

With T(i, j) meaning maximum profit selling up to the i-th apple after selling j apples.

In each DP step you have to choose the best between selling or not selling the current apple. If the amount of sold apples so far (j), divided by the number of apples you can sell by time unit (k) reaches the apple's "time to rot" (rot(i)), it cannot be sold.

One trick here is that you have to sort the apples by "time to rot" first.

---

Correctness

I'll paste Ilmari Karonen's comment here because it explains the algorithm correctness and shouldn't be just a comment.

Note that the correctness of this solution depends crucially on the observation that, if a certain subset of the apples can be sold at all, it can be sold in ascending order by expiry time. Thus, if you consider all the apples in ascending order by expiry time, the only decision you need to make for each apple is whether to sell it now or to not sell it at all

---

Implementation

Here's a simple recursive implementation in Python (that can easily be memoized for polynomial time):

This program also explains which apples must be chosen to maximize the outcome:

A = [(2, 3), (1, 1), (3, 4), (1, 2)]

def solve(A, k, i, j):
    if i>=len(A): return (0, [])
    ttr, value = A[i]
    if j/k >= ttr:
        return solve(A, k, i+1, j)
    else:
        answer, explanation = solve(A, k, i+1, j+1)
        return max((value+answer, [A[i]]+explanation), solve(A, k, i+1, j))

print solve(sorted(A), 1, 0, 0)

This outputs:

(9, [(1, 2), (2, 3), (3, 4)])

Answer 2

First sort your apples by time-to-rot.

If the slowest rotting apple takes X time-units to rot, then start from X and work toward 0 time-units. (Ben Voight observes that you actually only need min(time-to-sell-all-apples,time-until-last-apple-rots))

For each time-unit, select the most expensive apple that isn't yet rotted that wasn't previously selected, and mark it to be sold during this time unit. If there are no unselected apples unrotted, immediately jump to the time-unit of the next-slowest-rotting apple.

You now have a list of time-units from 0 to X, and an apple associated with each one. Sell the apples in this order.

I think this is optimal, but I'm not certain. It's a little counter-intuitive, because you choose which apple to sell at which time in the opposite order that they're actually sold in.

---

If these are your apples:

Index  1   2   3
Price  1  20  30
Time   1   3   3

Then we select an apple for each time slot from three to zero.

• First is time-3. The non-selected apples here are #2 (worth 20) and #3 (worth 30) We select #3 (because it's worth more) to be sold at time-3.
• The next time slot is time-2. There's only one non-selected apple not rotted here - #2 (worth 20), so we select it to be sold at time-2.
• The next time slot is time-1. There's only one non-selected apple not rotted here - #1 (worth 10), so we select that apple to be sold at time-1.
• The final time slot it time-0. There's no apples left, so we sell nothing at time-0.

I assume for my sample that that there is a zero time-slot, and that the apples rot after that time expired, but neither of these are required for the algorithm to work, they just alter the implementation.