# Making a recursive formula for finding amount of ways to spend money on beer

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?

## 2 Answers

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.

• 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$ – Levicia May 18 '18 at 12:26

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.