0
$\begingroup$

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following recursive formula where you either bought a beer and losing $P-i$ money, or passed the beer and went for the next in the array $i-1$. You cannot buy the same type of beer twice.

$$N(C,i)=\begin{cases} 0 & \quad \text{if } C<0\;||\; i<0 \\ 1 & \quad \text{if } C=0\\ N(C,i-1)+N(C-P_i,i-1) & \quad otherwise \end{cases} $$

I'm not certain how to prove the correctness of the algorithm. Especially because the assignment is about dynamic programming, and I can't find any repeated subproblems. The amount of money you will have will differ unless some of the different beers cost the same. I asked a fellow student who said the problem will always give overlapping subproblems. N(C,i) recursive tree The problem has also been talked about here (Making a recursive formula for finding amount of ways to spend money on beer), but I think my recursive formula is correct.

Sorry, if the question is unclear, or if I've done something wrong. It's the first time on stackexchange, and I think, this is the place to ask the question and not the mathmatics site.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

I figured it out.

Overlapping-subproblems:

  1. $P_i == P_{i_1}$: If two beers has the same price it will give overlapping subproblems. The assignment thinks this is okay.
  2. $P_i == P_{i-1}+P_{i-2}$: If a collection of beer has the same price as another collection of beers they will end up with the same parameter $C$. Because every left call doesn't change the value of $C$ it will give overlapping subproblems.

Proof of Correctness

I thought I had to prove the algorithm through induction with a mathematical equation. This wasn't the case. I had to prove that simple base-cases would give the correct value, and that the recursive calls would get closer to the 1st and 2nd statement and prove that the algorithm would eventually terminate.

  • Case 1: If $C = 0$, then $N(C,i)=1$
  • Case 2: If $i = 0$ and $C!=0$, then $N(C,i)=0$ (Had to edit my formula. The assignment specified that you had to use all your money)
  • and more...
Improve this answer
$\endgroup$
1
  • $\begingroup$ I am having some trouble understanding your solution. First of all, while it is true that overlapping subproblems can occur, this is not guaranteed so we cannot be sure that dynamic programming applies. Is this not true? Second, while your proof is intuitively true, it does not seem mathematically rigorous to me. Normally you would prove a recursive formula by induction, but you mention that this possibility is excluded. I wondered whether the proof maybe should be based on showing optimal substructure like it is done in numerous examples in CLRS (which i believe is your coursebook). $\endgroup$
    – sss
    Commented Oct 2, 2018 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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