Confusing Output for 0/1 Knapsack Problem

Question

I'm learning Dynamic Programming, and have the book Grokking Algorithms

The example given there uses these images/values:

When I run the code below, which is supposed to implement the 0/1 Knapsack Problem in Python, I get the following output:

+---+------+------+------+------+
| 0 |  0   |  0   |  0   |  0   |
| 0 | 1500 | 1500 | 1500 | 1500 |
| 0 | 1500 | 1500 | 2000 | 3500 |
| 0 | 1500 | 1500 | 2000 | 3500 |
+---+------+------+------+------+
3500

The solution is correct, but it looks like this is a coincidence, as the table generated by the code is different from that given in the image from the book.

Could someone please explain why the table generated by the code is different from the one in the book?

Could it be that the formula used to generate the table is different (as in different in effect - I can see that they are not identical)? The one in the book is:

# A Dynamic Programming based Python
# Program for 0-1 Knapsack problem
# Returns the maximum value that can
# be put in a knapsack of capacity W
from tabulate import tabulate


def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1]
                              + K[i - 1][w - wt[i - 1]],
                              K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]
    print(tabulate(K, tablefmt="pretty"))

    return K[n][W]


# Driver code
val = [1500, 2000, 3000]
wt = [1, 3, 4]
W = 4
n = len(val)
print(knapSack(W, wt, val, n))

user_16530078 · Answer

+---+------+------+------+------+
| 0 |  0   |  0   |  0   |  0   |
| 0 | 1500 | 1500 | 1500 | 1500 |  guitar
| 0 | 1500 | 1500 | 2000 | 3500 |  laptop
| 0 | 1500 | 1500 | 2000 | 3500 |  stereo
+---+------+------+------+------+
3500

Your listing is [guitar, laptop, stereo], however in the solution of the author, listing is [guitar, stereo, laptop]. That's why your tables are different and that's all. Your solution is indeed correct. Try to run your solution with the listing of the author:

from tabulate import tabulate

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1]
                              + K[i - 1][w - wt[i - 1]],
                              K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]
    print(tabulate(K, tablefmt="pretty"))

    return K[n][W]


# Driver code
val = [1500, 3000, 2000]
wt = [1, 4, 3]
W = 4
n = len(val)
print(knapSack(W, wt, val, n))

Output:

+---+------+------+------+------+
| 0 |  0   |  0   |  0   |  0   |
| 0 | 1500 | 1500 | 1500 | 1500 |   guitar
| 0 | 1500 | 1500 | 1500 | 3000 |   stereo
| 0 | 1500 | 1500 | 2000 | 3500 |   laptop
+---+------+------+------+------+
3500

Confusing Output for 0/1 Knapsack Problem

1 Answers