2
$\begingroup$

Take:

  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?

_

EDIT:

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.

KP:

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

$\endgroup$
  • $\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$ – Yuval Filmus Dec 7 '18 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$ – Yuval Filmus Dec 7 '18 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 '18 at 3:03
2
$\begingroup$

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.

$\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.