Search code examples
pythonsyntaxpseudocode

python notation form textbook

I have a code snipped from my algorithms text book and i'm have a hard time understanding it.

K(0) = 0
for w = 1 to W
    K(w) = max{K(w - w_i)+vi:w_i<=w}
return K(W)

i'm confused as to whats happening on line 3 what does the colon mean here? can this be written in a different way?

Solution

  • This doesn't look like python. It seems that K is supposed to be an array, but indices are indicated by square brackets in python, so K[0] = 0

    And the for w = 1 to W doesn't work in python at all, it would be more like this: for w in range(1, W+1):

    As for what the pseudo code does: It looks like for each element of K, it calculates the maximum of all previous values and adds vi.

    for w in range(1, W+1):
    K[w] = max(K[w - w_i] + vi for w_i in range(1, w+1))

    But vi doesn't seem to change, so for positive vi, this produces simply a linearly ascending array (i.e. [0, 2, 4, 6, ... for vi = 2), and for negative it just repeats vi over and over: [0, -3, -3, -3, ... for vi = -3

    Since it returns only the last value of the array, it could be simplified to 

    return W*vi if vi>0 else vi