0/1 knapsack problem recursive

by

The 0/1 Knapsack problem, as discussed, seeks to maximize the total value of items that can be included in a knapsack without exceeding its weight capacity. Each item has a specified weight and value, and the objective is to determine the optimal subset of items to include. Unlike the dynamic programming approach, solving the 0/1 Knapsack problem using recursion involves exploring all possible combinations of items to find the one that offers the maximum value within the weight constraint.

Recursive Approach

The recursive approach to the 0/1 Knapsack problem involves making a decision for each item: whether to include it in the knapsack or not. This creates a binary decision tree where each node represents a state defined by the current item and the remaining capacity of the knapsack. The algorithm explores this tree to find the maximum value obtainable.

  1. Base Cases:
    • If no items are left or the capacity of the knapsack becomes 0, the maximum value that can be obtained is 0.
  2. Choice Diagram:
    • For each item, there are two possibilities:
      • Include the item: If the item’s weight is less than or equal to the remaining capacity of the knapsack. This reduces the remaining capacity and moves to the next item.
      • Exclude the item: Skip the current item and move to the next item.
    • The maximum value obtained will be the maximum of these two choices.
  3. Recursive Calls:
    • The algorithm makes recursive calls to itself with updated parameters based on the choices made.
Kotlin
fun knapSack(W: Int, wt: IntArray, val: IntArray, n: Int): Int {
    // Base Case
    if (n == 0 || W == 0)
        return 0

    // If weight of the nth item is more than Knapsack capacity W,
    // then this item cannot be included in the optimal solution
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1)

    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else
        return maxOf(
            val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
            knapSack(W, wt, val, n - 1)
        )
}

// Example usage
fun main() {
    val val = intArrayOf(60, 100, 120)
    val wt = intArrayOf(10, 20, 30)
    val W = 50
    val n = val.size
    println("Maximum value achievable is: ${knapSack(W, wt, val, n)}")
}

Explanation:

  • The function knapSack is defined with four parameters: the remaining capacity of the knapsack W, the array of item weights wt, the array of item values val, and the number of items n.
  • It starts by checking the base cases: if n or W is 0, it returns 0 as no value can be obtained.
  • If the weight of the current item (wt[n-1]) is more than the remaining capacity W, the item cannot be included, and the function calls itself for the remaining items (n-1).
  • If the item can be potentially included, the function calculates the maximum value by considering both including and excluding the current item. It includes the item’s value and subtracts its weight from the remaining capacity if included.
  • The main function demonstrates using the knapSack function to find the maximum value achievable with a given set of items and knapsack capacity, printing the result.

Leave a Comment