algorithm - Sell rotting apples in time -

i stuck regarding following question. have idea? of course, brute-forcing permutations solves problem. however, there approach?

suppose sell apples , each apple has associated "time rot" until cannot sold anymore.

suppose apples have separate price dependent on aesthetics. price constant until apple has rotten, becomes zero.

selling apple takes constant time, therefore cannot sell them first k apples.

in order should sell rotting apples in order maximize outcome?

do have hints type of literature here? operations research or queueing theory?

i think simple dynamic programming 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 i-th apple after selling j apples.

in each dp step have choose best between selling or not selling current apple. if amount of sold apples far (j), divided number of apples can sell time unit (k) reaches apple's "time rot" (rot(i)), cannot sold.

one trick here have sort apples "time rot" first.

---

correctness

i'll paste ilmari karonen's comment here because explains algorithm correctness , shouldn't comment.

note correctness of solution depends crucially on observation that, if subset of apples can sold @ all, can sold in ascending order expiry time. thus, if consider apples in ascending order expiry time, decision need make each apple whether sell or not sell @ all

---

implementation

here's simple recursive implementation in python (that can memoized polynomial time):

this program explains apples must chosen maximize 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)])