Classic DP Problems: Knapsack & Longest Common Subsequence (LCS)

1. 0/1 Knapsack Problem

Given items each with weight and value, and a knapsack with capacity W, select items to maximize value without exceeding capacity.

Approach

• Use dynamic programming to explore including or excluding each item.
• Create a DP table where dp[i][w] represents max value using first i items with capacity w.
• Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) if weight[i] ≤ w; else exclude item.

Python Code (Bottom-Up DP)

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(1, W+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
W = 7
print("Max value in Knapsack:", knapsack(weights, values, W))  # Output: 9

2. Longest Common Subsequence (LCS)

Find the longest subsequence common to two sequences, which may not be contiguous but maintains order.

Approach

• Use dynamic programming with a 2D table dp where dp[i][j] stores LCS length for first i chars of string 1 and first j chars of string 2.
• If characters match: dp[i][j] = 1 + dp[i-1][j-1]
• If not match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Python Code (Bottom-Up DP)

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

X = "AGGTAB"
Y = "GXTXAYB"
print("Length of LCS:", lcs(X, Y))  # Output: 4