Design of Algorithms

Dynamic Programming

Dynamic Programming

Table of Contents

Knapsack: bottom up

function KnapSack(v[1..n], w[1..n], W):
    # initialise first column with 0
    for i from 0 to n:
        K[i, 0] = 0
    
    # initialise first row with 0
    for j from 1 to W:
        K[0, j] = 0;

    # iterate over table
    for i from 1 to n:
        for j from 1 to W:
            if j < w[i]:
                K[i, j] = K[i-1, j]
            else:
                K[i, j] = max(K[i-1, j], K[i-1, j-w[i]] + v[i])

    return K[n,W]

Edit this page.