1. KP recurrence relation

$ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0

  1. CCP recurrence relation

$ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0

I don't understand (much as I've researched) exactly what the reasoning is behind KP comparing in both cases (take the element/don't take it) to the above row $('k-1')$ while CCP only does this when it doesn't take the coin (the same number that's a row above in the same column persists).

To evaluate the case where the coin is taken, CCP says to go back on the same row as much columns as you get when subtracting the coin value of that row from the column you're in . Then it says to add 1 (because you'd be taking the coin).

Supposing I understood this well enough, the latter logic makes perfect sense to me. I don't see the need for KP to go up a row when taking the element (I see why it adds 'v' and goes back a number of columns, it's just the $'k-1'$ that baffles me)

What's the logic behind this?



Underlined in red you'll find what I'm referring to, more especifically.

Knapsack 0-1 Problem:

Take the 24 : it's the result of comparing the 15 directly above it (not taking the element) to the 15 up and to the left (taking the element) . This last 15 is not on the same row as 24 is.


See source: http://www.mafy.lut.fi/study/DiscreteOpt/DYNKNAP.pdf

Coin Change Problem:

Goes back on the same row where our starting point is(case where coin is taken).

enter image description here

See source: (page 2): http://condor.depaul.edu/rjohnson/algorithm/coins.pdf

  • $\begingroup$ There seems to be some background missing here. What is the Knapsack problem (there are several variants)? What is the coin changing problem? What do the various variables and functions stand for? $\endgroup$ Dec 7, 2018 at 1:09
  • 1
    $\begingroup$ The recurrences are presumably accompanied by proofs that they work correctly. The proofs should explain why they look the way they do. $\endgroup$ Dec 7, 2018 at 1:12
  • $\begingroup$ @YuvalFilmus It'd be the 0-1 Knapsack problem. The coin change problem would be the one where an amount is given and you're prompted to give it back in coin change (each coin can be picked more than once in a given operation). I see they work, it's just that one detail that I can't follow. It seems to me there's no reason why KP couldn't just check back against the value back on the same row. I've edited my post to add some visual references, so it may be easier to see what I'm referring to. $\endgroup$
    – degausser
    Dec 7, 2018 at 3:03

2 Answers 2


The knapsack problem only allows you to add each item once. Subtracting from $k$ is, in a sense, iterating through the items and resolving a different one each recursion.

Put another way, if you didn't subtract 1 from $k$, you'd be able to add the same element multiple times.


In CC you can use same coin INFINITE times. But in KP you can use the same weight, not more than once. Check http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf

To consider all the subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset (2) not included in the optimal set.

Therefore, the maximum value that can be obtained from n items is the max of the following two values.

1) Maximum value obtained by n-1 items and W weight (excluding nth item).

2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

If the weight of the nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.


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.