0-1 Knapsack

(i).0-1 Knapsack -Recursive

Python Code


def knapsack_recursive(values, weights, capacity, n):
    # Base case: no items or no capacity
    if n == 0 or capacity == 0:
        return 0
    
    # If the weight of the current item exceeds the capacity, skip it
    if weights[n - 1] > capacity:
        return knapsack_recursive(values, weights, capacity, n - 1)
    
    # Return the maximum value of including or excluding the current item
    return max(
        values[n - 1] + knapsack_recursive(values, weights, capacity - weights[n - 1], n - 1),
        knapsack_recursive(values, weights, capacity, n - 1)
    )

# Example usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
n = len(values)
result = knapsack_recursive(values, weights, capacity, n)
print("Maximum value:", result)

(ii). 0-1 Knapsack - Memoization(TOP DOWN)

Python Code


def knapsack_topdown(values, weights, capacity, n, memo):
    if n == 0 or capacity == 0:
        return 0
    
    if memo[n][capacity] != -1:
        return memo[n][capacity]
    
    if weights[n - 1] > capacity:
        memo[n][capacity] = knapsack_topdown(values, weights, capacity, n - 1, memo)
        return memo[n][capacity]
    
    memo[n][capacity] = max(
        values[n - 1] + knapsack_topdown(values, weights, capacity - weights[n - 1], n - 1, memo),
        knapsack_topdown(values, weights, capacity, n - 1, memo)
    )
    return memo[n][capacity]

def knapsack(values, weights, capacity):
    n = len(values)
    memo = [[-1 for _ in range(capacity + 1)] for _ in range(n + 1)]
    return knapsack_topdown(values, weights, capacity, n, memo)

# Example usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
result = knapsack(values, weights, capacity)
print("Maximum value:", result)

(iii). 0-1 Knapsack - Tabulation(Bottom UP)

Python Code


def knapsack_bottomup(values, weights, capacity):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                    dp[i - 1][w]
                )
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][capacity]

# Example usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
result = knapsack_bottomup(values, weights, capacity)
print("Maximum value:", result)

1. Subset Sum

Python Code


def subsetSum(arr,n,sm):
    dp = [[False for _ in range(sm+1)]for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = True
    for i in range(1,sm+1):
        dp[0][i] = False
        
    for i in range(1,n+1):
        for j in range(1,sm+1):
            if arr[i-1]<=j:
                dp[i][j] = dp[i-1][j - arr[i-1]] or dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][sm]
    
arr = [2,3,7,8,10]
sm =11

res =  subsetSum(arr,len(arr),sm)
print(res)

2. Equal Sum Partition

Python Code


def EqualSumPartition(arr,n,sm):
    dp = [[False for _ in range(sm+1)]for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = True
    for i in range(1,sm+1):
        dp[0][i] = False
        
    for i in range(1,n+1):
        for j in range(1,sm+1):
            if arr[i-1]<=j:
                dp[i][j] = dp[i-1][j - arr[i-1]] or dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][sm]
    
arr = [1,5,11,5,1]
sm =sum(arr)
if sm%2==0:
    res = subsetSum(arr,len(arr),sm//2)
    print(res)
else:
    print(False)

3. Count of subset sum

Python Code


def count(arr,n,sum):


    dp = [[0]*(sum+1) for _ in range(n+1)]
            
    for i in range(0,n+1):
        dp[i][0] =1
    for i in range(1,n+1):
        for j in range(sum+1):
            if arr[i-1]<=j:
               dp[i][j] = dp[i-1][j - arr[i-1]] + dp[i-1][j]
           else:
               dp[i][j] = dp[i-1][j]
    return dp[-1][-1]%mod

arr = [1,2,3,4]
n = len(arr)
res = count(arr,n,sum(arr))
print(res)