Let's say we are given $n$ types of drinks, integer $m$ representing the budget we have and integer $d$ representing the cost of delivery when we order some drinks. For each of the $n$ drinks we are given $P_i \text{ the price of i-th drink and } E_i - \text{expire date}$. For example $(3, 2)$ is representing drink with price $3$ for one bottle and the second number means that this drink can be used at most $2$ days after we buy it. One cannot drink drinks that have expired date of usage and one must drink exactly once per day.

We can order as many drinks as we want from each type, but each time we order we are paying $d$ dollars for delivery. Notice that the delivery doesn't matter in the day, so we can buy drink with exprite date $2$ and used it either today, tomorrow, or the day after tomorrow.

We want to maximize the number of drinks we will buy and drink.

I think that this problem can be solved with greedy strategy, but I'm not able to find anything that can lead to correct result and good time complexity.

Here are some things that I got so far:

We don't want to buy things that will be expired, so from each drink with price $P_i$ we will spend at most $P_i \cdot(E_i + 1)$

Because we may have big budget, it is good to find one way of buying drinks and use it couple times, until we don't run out of money from the budget.

We will first buy the cheaper drinks and for the more expensive ones we should decide should we make a new order, or buy some drinks from the next type.

I didn't got anything that lead to correct strategy, so please share some of your ideas.

  • 1
    $\begingroup$ You haven't yet told us what you're trying to do with this list of drinks. Are you trying to maximise/minimise something? What exactly? $\endgroup$ Jan 3 '19 at 12:15
  • $\begingroup$ Sorry, I missed that, we want to maximize the number of drinks we will buy, I will add to the post now $\endgroup$ Jan 3 '19 at 13:01
  • $\begingroup$ OK, but I still don't see how the expiry date has any effect here. You probably need to incorporate this into the objective function somehow. $\endgroup$ Jan 3 '19 at 13:13
  • $\begingroup$ It has big effect, because when you buy the drink, you should drink it before it expires, otherwise you are not allowed to drink it. I added this to the text. $\endgroup$ Jan 3 '19 at 13:52
  • $\begingroup$ But you don't say anything about when you must/may drink it. Why not drink everything as soon as you buy it? If you do that, you never have to worry about any expiry dates. $\endgroup$ Jan 3 '19 at 13:53

It’s not very difficult really, assuming we only care about the cost and don’t have any preferences for drinks.

If we want to make a single order that lasts for n days as cheap as possible, we order the cheapest drink with expiry k, for each 0 <= k < n. That supply costs the cost of the drinks plus d. We can calculate this cost for 1 <= n <= E+1, where E is the longest expiry of any drink.

If we want drinks for N days, we make 1 or more orders to minimise the total cost. We may assume the orders are ordered by size in descending order (and if we find the best sequence of orders with this restriction, we can rearrange it any way we like). Finding the best orders is now a simple dynamic programming problem.

If you are looking for something complicated, it’s not needed.

  • $\begingroup$ In the second paragraph: What should we do if there isn't drink with expire at day k, also how can we merge this all in one since we have limited budget on how we can spend money, also did you note that we can buy each drink more than once. $\endgroup$ Jan 3 '19 at 22:07
  • $\begingroup$ If nothing expires at day k, we obviously use something that expires later. Covering the maximum number of days with a given budget is a slight change in the dynamic programming algorithm. All your questions you could have answered easily yourself. It’s your problem in the end. $\endgroup$
    – gnasher729
    Jan 4 '19 at 10:11
  • $\begingroup$ We want drinks for N days, I believe. I don't yet see how ordering orders by size helps with DP. In the DP I have in mind, subproblems are of the form "What is the cheapest solution for the first $i$ days in which the last order happens on day $i-j$?", for all $1 \le i \le N$ and $0 \le j \le E$. So there are $O(NE)$ subproblems, each taking $O(1)$ time to solve if we spend $O(E+n\log n)$ preprocessing time to build a table $C$ such that $C[k]$ is the cost of the cheapest drink that lasts at least $k$ days, for $O(NE+n\log n)$ overall. Is that also the time complexity of your approach? $\endgroup$ Jan 4 '19 at 16:50
  • $\begingroup$ If we have n orders, they could be arranged in n! possible orders. Requesting some ordering simplifies the problem exponentially. $\endgroup$
    – gnasher729
    Jan 5 '19 at 13:23
  • $\begingroup$ E can go up to 10^9, so I dont believe we can do any DP solutions that save many things $\endgroup$ Jan 5 '19 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.