How to fill a knapsack table when using recursive dynamic programming
<p><strong>* NOT HOMEWORK *</strong></p>

<p>I have implemented the knapsack in python and am successfully getting the best value however I would like to expand the problem to fill a table with all appropriate values for a knapsack table of all weights and items.</p>

<p>I've implemented it in python which I'm new to so please advise me if theres anything I could improve upon however the concepts should work in any language.</p>

<pre><code>values, weights, table = [], [], [[]]

def knapsack(i, W):
    global weights, values, table, counter
    if (i &lt; 0):
        # Base case
        return 0
    if (weights[i] &gt; W):
        # Recursion
        return knapsack(i - 1, W)
    else:
        # Recursion
        return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))

def main():
    global values, weights, table
    W = int(input())
    values = list(map(int, input().split()))
    weights = list(map(int, input().split()))
    # initalise table with 0's
    table = [[0 for i in range(W)] for i in range(len(values))]
    for i in range(len(values)):
        for j in range(W):
            table[i][j] = 0
    # Fill table
    print("Result: {}".format(knapsack(len(values) - 1, W)))
    printKnapsack(W)

if __name__ == '__main__':
    main()
</code></pre>

<p>I also have this print table method which is unrelated but just so you can see what I'm outputting it as:</p>

<pre><code>def printLine(W):
    print(" ",end="")
    for i in range(W + 1):
        print("-----",end="")
    print("")

def printKnapsack(W):
    global table
    print("\nKnapsack Table:")
    printLine(W)
    print("| k\w |", end="")
    for i in range(W):
        print("{0: &gt;3} |".format(i + 1), end="")
    print("")
    printLine(W)
    for i in range(len(values)):
        print("|  {}  |".format(i+1), end="")
        for j in range(W):
            print("{0: &gt;3} |".format(table[i][j]), end="")
        print("")
        printLine(W)
</code></pre>

<p>This is the sample input:</p>

<pre><code>10
18 9 12 25
5 2 4 6
</code></pre>

<p>This is what is should output:</p>

<pre><code>Result: 37

Knapsack Table:
 -------------------------------------------------------
| k\w |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 |
 -------------------------------------------------------
|  1  |  0 |  0 |  0 |  0 | 18 | 18 | 18 | 18 | 18 | 18 |
 -------------------------------------------------------
|  2  |  0 |  9 |  9 |  9 | 18 | 18 | 27 | 27 | 27 | 27 |
 -------------------------------------------------------
|  3  |  0 |  9 |  9 | 12 | 18 | 21 | 27 | 27 | 30 | 30 |
 -------------------------------------------------------
|  4  |  0 |  9 |  9 | 12 | 18 | 25 | 27 | 34 | 34 | 37 |
 -------------------------------------------------------
</code></pre>

<p>I have tried multiple different lines in the <code>knapsack(i, W)</code> function to add elements to the table and I've drawn it out but I can't understand how the recursion is working well enough to figure out what indexes to put in to add the unravelled recursive call values to.</p>

<p>This is the method I have to fix.</p>

<pre><code>def knapsack(i, W):
    global weights, values, table, counter
    if (i &lt; 0):
        # Base case
        return 0
    if (weights[i] &gt; W):
        # Recursion
        table[?][?] = ?
        return knapsack(i - 1, W)
    else:
        # Recursion
        table[?][?] = ?
        return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))
</code></pre>

<p>In your recursive algorithm you just can't get full filled table, because this step skip a lot:</p>

<pre><code>return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))
</code></pre>

<p>I can sudgest you this solution:</p>

<pre><code>def knapsack(i, W):
    global weights, values, table, counter
    if (i &lt; 0):
        # Base case
        return 0
    if (weights[i] &gt; W):
        # Recursion
        table[i][W-1] = knapsack(i - 1, W)
        return table[i][W-1]
    else:
        # Recursion
        table[i][W-1] = max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))
        return table[i][W-1]
</code></pre>

<p>In resulted table non-zero cells means that your algorithm step through here and got this intermediate solution. Also you can run your algorithm more than once with different input values and got full-filled table.</p>

<p>Hope this helped</p>

python recursion dynamic-programming knapsack-problem bottom-up