Unbounded Knapsack

(i). Unbounded Knapsack -Recursive

Python Code


def unbounded_knapsack_recursive(values, weights, capacity, n):
    # Base case: no capacity or no items
    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 unbounded_knapsack_recursive(values, weights, capacity, n - 1)
    
    # Return the maximum value of including or excluding the current item
    return max(
        values[n - 1] + unbounded_knapsack_recursive(values, weights, capacity - weights[n - 1], n),
        unbounded_knapsack_recursive(values, weights, capacity, n - 1)
    )

# Example usage
values = [10, 30, 20]
weights = [5, 10, 15]
capacity = 100
n = len(values)
result = unbounded_knapsack_recursive(values, weights, capacity, n)
print("Maximum value:", result)

(ii). Unbounded Knapsack - Memoization(TOP DOWN)

Python Code


def unbounded_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] = unbounded_knapsack_topdown(values, weights, capacity, n - 1, memo)
        return memo[n][capacity]
    
    memo[n][capacity] = max(
        values[n - 1] + unbounded_knapsack_topdown(values, weights, capacity - weights[n - 1], n, memo),
        unbounded_knapsack_topdown(values, weights, capacity, n - 1, memo)
    )
    return memo[n][capacity]

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

# Example usage
values = [10, 30, 20]
weights = [5, 10, 15]
capacity = 100
result = unbounded_knapsack(values, weights, capacity)
print("Maximum value:", result)

(iii). Unbounded Knapsack - Tabulation(Bottom UP)

Python Code


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

# Example usage
values = [10, 30, 20]
weights = [5, 10, 15]
capacity = 100
result = unbounded_knapsack_bottomup(values, weights, capacity)
print("Maximum value:", result)

1. Rod Cutting

Python Code


price = [1,5,8,9,10,17,17,20]
length =[1,2,3,4,5,6,7,8]
length =8 
n = len(price)

dp = [[[0] for _ in range(price+1)]for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
for i in range(1,sm+1):
    dp[0][i] = 0
        
for i in range(1,n+1):
    for j in range(1,price+1):
        if length[i-1]<=j:
            dp[i][j] = max(price[i-1]+dp[i][j - dp[i-1]], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][price])