0
$\begingroup$

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this.

The information available is that there are $n$ different beers with different prices, the $i$th beer has a price $p_i$. Students have $C$ amount of money

How would you make a recursive formula for the amount of ways students can spend exactly $C$ money on beer?

$\endgroup$
0
$\begingroup$

The $n$-the beer has price $p_n$. You can use $k$ items of beer $n$, provided $k\cdot p_n\le C$. The remaining money can be used for beers $1$ to $n-1$. That gives a recursive approach.

$\endgroup$
  • $\begingroup$ so if i were to make that as a recursive formula it would be something like: \begin{equation} N(C, i)=\begin{cases} N(C, i)=0 & \text{if $C=0$}\\ N(C, i)= k \cdot p_i & \text{if $K \cdot p_n \leq C$}\\ N(C, i)= C-p_i & \text{if $C>0$ and $K \cdot p_n > C$ } \end{cases} \end{equation} I'm actually unsure on how to formulate "$1$ to $n-1$ $\endgroup$ – Levicia May 18 '18 at 12:26
0
$\begingroup$

My attempt is

$$ N(C)=\left\{ \begin{align} &0&C<p_{min}\\ &1&C=p_{min}\\ &\displaystyle\sum_i N(C-p_i)&\text{other cases} \end{align} \right. $$

The summation part solves your problem of going through 1 to n.

Implementing this on the computer gives correct answers.

$\endgroup$

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.