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

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top