def knapsack_dp(val, wt, wt_cap):
    """0-1 Knapsack Problem by bottom-up dynamic programming.

    Time complexity: O(nC), where 
      - n is the number of items, and 
      - C is the weight capacity.
    Space complexity: O(nC).
    """
    n = len(wt)

    # Create tabular T of n x (wt_cap+1).
    T = [[None] * (wt_cap + 1) for i in range(n)]
 
    # For empty cap, no value can be added.   
    for i in range(n):
        T[i][0] = 0
    
    # For 1s item only.
    for j in range(1, wt_cap + 1):
        if wt[0] <= j:
            T[0][j] = val[0]
        else:
            T[0][j] = 0

    for i in range(1, n):
        for j in range(1, wt_cap + 1):
            if wt[i] <= j:
                # Can be put: to put or not to put.
                T[i][j] = max(val[i] + T[i - 1][j - wt[i]], T[i - 1][j])
            else:
                # Cannot be put.
                T[i][j] = T[i-1][j]

    return T