2

I have solved a programming problem with a Equation. But can't simulate this equation briefly. Anyone can help me?

Question: I have $n$ rubles initially. The cost of one plastic litre bottle, the cost of one glass litre bottle, and the money one can get back by returning an empty glass bottle are $a$, $b$ and $c$, respectively, where $1\leqslant a\leqslant10^{18}$, $1\leqslant c<b\leqslant10^{18}$. I need the maximum number of litre I can drink with my rubles.

Number of glass litre is $\dfrac{n-c}{b-c}$.

Then total litre will be:

$t1 = \dfrac{n-c}{b-c}$

${n = n -(b-c)*t1}$

$t2 = \frac{n}{a}$

$ans = t1 + t2$

How this simulation has come? Can anyone please elaborate?

Example: $n=10$ $a=11$ $b=9$ $c=8$

Answer will be $2$

aspile
  • 121

1 Answers1

1

Let $p$ and $g$ be the number of plastic and glass bottles purchased, respectively. Assume that you return all glass bottles. Consider the problem of maximizing $p+g$ subject to linear constraints: \begin{align} a p + (b - c) g &\le n \\ p,g &\ge 0 \end{align} For $(n,a,b,c)=(10,11,9,8)$ the optimal solution is $(p,g)=(0,10)$, but this solution is not implementable because you cannot simultaneously buy and return a glass bottle.

One way around this is to introduce a time index: for time $t=1,\dots,T$, let $p_t$ be the number of plastic bottles purchased, let $g_t$ be the number of glass bottles purchased, let $r_t$ be the number of glass bottles returned, and let $m_t$ be the amount of money available after purchases. The new problem is to maximize $\sum_t (p_t + g_t)$ subject to: \begin{align} n &= a p_t + b g_t + m_t &&\text{for $t=1$} \\ m_{t-1} + c r_{t-1} &= a p_t + b g_t + m_t &&\text{for $t>1$} \\ r_t &\le g_t &&\text{for all $t$} \\ p_t, g_t, r_t, m_t &\ge 0 &&\text{for all $t$} \end{align} You will need to impose integrality of $p_t$, $g_t$, and $r_t$. Without loss of optimality, you can assume $r_t=g_t$.

RobPratt
  • 45,619
  • Well. Thank you for your explanation. But I have mentioned a Formula to solve this problem. and That is correct. Need to understand that. Not clear yet with your try and my given formula. – aspile May 05 '20 at 20:27
  • Your formula does not involve $a$, so I don't think it can be correct. Yes, $(n,a,b,c)=(10,11,9,8)$ yields an optimal solution with $0$ plastic bottles and $2$ glass bottles. But $(n,a,b,c)=(10,1,9,8)$ yields an optimal solution with $10$ plastic bottles and $0$ glass bottles. – RobPratt May 05 '20 at 20:36
  • I am extremely sorry to say that I have edited my Question. See that equation will solve for all cases. But how this simulation is coming to solution. Need to know that. – aspile May 05 '20 at 20:50
  • For $(n,a,b,c)=(10,1,10,1)$, your formula yields $t_1+t_2=1+1=2$, but optimal is $10$. – RobPratt May 05 '20 at 21:04
  • Are you sure? My formula is giving 10 – aspile May 05 '20 at 21:12
  • $t_1=(n-c)/(b-c)=(10-1)/(10-1)=1$, then $n=n-(b-c)t_1=10-(10-1)1=1$, and then $t_2=n/a=1/1=1$, so $t_1+t_2=1+1=2$. – RobPratt May 05 '20 at 21:17
  • Yes you are correct. I am wrong!!. But I need the maximum number of litre I can drink with my rubles what I have mentioned!!! In this case I don't need to drink glass bottle.. Right?? – aspile May 05 '20 at 21:34
  • (n/a) will be the answer then... – aspile May 05 '20 at 21:35