Greedy Florist

  • + 5 comments

    Just to clarify, as some people seem to be having a few problems. If Anne and Bob go to buy flowers [1,2,7,9,100], then the minimum price is 130. Why?

    Assume only one person buys the flowers in the given order. So, she pays (1)1+(2)2+(3)7+(4)9+(5)100 = 562. From this we can see that order matters; for example, if she buys them in the opposite order, we get (1)100+(2)9+(3)7+(4)2+(5)1 = 152! Even without a second person, we can see that an opportunistic order drastically improves the price.

    So, hopefully without giving the problem away, what we would want to do is assign the flowers to Anne and Bob in such a way not only to reduce the total number each person purchases [so that no person will buy an ith flower larger than is necessary (so that their ith multiplyer will be no larger than is necessary for any given flower)], but to assign the order they buy their flowers responsibly as well.
    Note: the oder of the people does not affect the price, only the order of flowers purchased by each person.