Yesterday we bought some strawberries, cherries, apricots, and plums at the local farmers market. Infact we bought more than we can possible consume before some of the fruit spoils. The problem under consideration is how to minimize the total of amount of spoiled fruit.

This problem is interesting since different fruits spoil at different rates. I’ll consider the simplest case of just two types of fruits. There are different possible models for the rate of fruit spoilage. I think the simplest one is to assume that the percent of good fruit that spoils in a day increases as a linear function.

As an example we assume the following table for the percent of strawberries that spoil on a particular day

…………………Percent of fruit that spoils

Day 0……………………..0%

Day 1……………………33%

Day 2……………………66%

Day 3………………….100%

By the above table, on day two 66% of the strawberries that weren’t spoiled at the beginning of day two, are spoiled by the end of day two. For convenience sake I assume that we consume fruit at the end of a day.

Table for cherry spoilage

…………………….Percent spoiled

Day 0……………………..0%

Day 1……………………25%

Day 2……………………50%

Day 3…………………..75%

Day 4…………………100%

Now, given 100 strawberries, 100 cherries and the ability to consume 20 pieces of fruit per day, how should we schedule our fruit consumption to minimize the amount of fruit that spoils (i.e. goes unconsumed.)

My solution is to use a greedy algorithm, I’m not positive that it minimizes total spoilage but I believe it does (Another possibility is to use linear programming but I like the greedy algorithm more.)

The algorithm is as follows

Given two goods A and B, percent X of A will go bad the next day, percent Y of B will go bad the next day, we have n pieces of fruit A, m pieces of fruit B, and we can consume p pieces of fruit (where p Y.

The amount of fruit that spoils, S = X * (n – n1) + Y*(m – m1), where n1 and m1 are the amount of fruit A and B we consume respectively, and n1 + m1 = p.

Now note that n1 = p – m1, obtaining S = X*(n-p + m1) + Y*(m – m1) = X*n – X*p +X*m1 + Y*m – Y*m1 = X*(n-p)+Y*m +m1*(X-Y)

Looking at S, it’s apparent that S is minimized when m1 is minimized, that is n1 is maximized. So

we should consume the strawberries first and then consume the cherries.

That’s all for today.

### Like this:

Like Loading...