Recursive formula for finding ways to spend x amount of money on y items

Question

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?

The closest i can seem to think would be:

\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_1...p_{n-1} & \text{if $C>0$ and $K \cdot p_n > C$ } \end{cases} \end{equation}

However the 3rd case doesn't make sense unless i can somehow say where $C - p_1...p_{n-1}=0$ Then i would have for when we have no money, for $k \cdot p_n$ amount of beer, and then the final case should be for using the remaining money after the middle case, anyone able to help?

Answer 1

If the order of the beers you buy doesn't matter, we can solve it by restricting ourselves to buying beers in the order they appear on the menu. This allows us to write a recurrence with two parameters.

Let $n(c,t)$ be the way to spend $c$ money on beers such that every beer you buy is among the $t$ first ones in your list.

Then we have

$$ n(c,t) = \begin{cases} 0 & \text{if }c<0\text{ or } t<1 \\ 1 & \text{if }c=0 \\ n(c,t-1) + n(c-p_t,t) & \text{otherwise} \end{cases} $$

This is still within the general paradigm of dynamic programming.

Answer 2

This is a standard algorithms and data structures exercise. The recursion is $$ N(C) = \sum_i N(C - p_i) $$ with the appropriate base cases: $N(C) = 0$ if $C \le 0$.

The logic is to find all the ways to continue after buying just one beer.

The usual computer science exercise asks you to return the lists of possible beer choices, not just the number of beers bought.

Edit in response to comment.

@HenningMakholm is right: this counts the order in which the beers are bought. Answering the question as asked is harder. I won't try here, but will leave this not quite answer.

You could look up knapsack problems and algorithms for making change to see solutions.