0/1 Knapsack using DP

by

The 0/1 Knapsack problem is a fundamental problem in combinatorial optimization. Given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, the objective is to maximize the total value of items that can be included in the knapsack without exceeding its weight capacity. Each item can either be included or excluded (hence the name “0/1”), and the challenge is to find the optimal subset of items that maximizes value within the weight limit.

Given:

  • A set of n items.
  • Each item has a weight wt[i] and a value val[i].
  • A knapsack with a weight capacity W.

The task is to find:

  • The maximum total value of items that can be included in the knapsack without exceeding its weight capacity.

Dynamic Programming Approach

Dynamic programming is well-suited for the 0/1 Knapsack problem because it involves breaking down the problem into smaller subproblems and solving each subproblem just once, storing the results in a table to avoid recalculating them.

  1. Initialization:
    • Create a 2D array dp of size (n+1) x (W+1) where n is the number of items and W is the knapsack capacity. Initialize all elements to 0.
    • dp[i][w] represents the maximum value that can be attained with the first i items and a knapsack capacity of w.
  2. Fill the DP Table:
    • Iterate over each item (i) and each possible weight (w) up to the maximum capacity W.
    • For each item, decide whether to include it in the knapsack. This depends on whether including the item leads to a higher value than excluding it, without exceeding the capacity.
    • Update dp[i][w] accordingly.
  3. Optimal Solution:
    • The value dp[n][W] will contain the maximum value that can be attained within the given weight capacity.
Kotlin
fun knapSack(W: Int, wt: IntArray, val: IntArray, n: Int): Int {
    // DP Table
    val dp = Array(n + 1) { IntArray(W + 1) }

    // Build table dp[][] in a bottom-up manner
    for (i in 0..n) {
        for (w in 0..W) {
            if (i == 0 || w == 0)
                dp[i][w] = 0
            else if (wt[i - 1] <= w)
                dp[i][w] = maxOf(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else
                dp[i][w] = dp[i - 1][w]
        }
    }

    return dp[n][W] // Return the maximum value that can be stored in the knapsack
}

// Example usage
fun main() {
    val val = intArrayOf(60, 100, 120)
    val wt = intArrayOf(10, 20, 30)
    val W = 50
    val n = val.size
    println(knapSack(W, wt, val, n))
}

Explanation:

  • The function knapSack calculates the maximum value that can be achieved within the given weight limit W.
  • It initializes a 2D array dp to store the maximum value that can be achieved using the first i items given a knapsack capacity of w.
  • It iterates over each item and capacity, updating the dp table based on whether including the current item is beneficial.
  • If including an item increases the total value without exceeding capacity, the item is considered included in the optimal subset.
  • The function returns the value at dp[n][W], which represents the maximum value that can be obtained for the entire set of items within the knapsack’s weight limit.
  • The main function demonstrates an example usage of knapSack, printing the maximum value that can be achieved for a given set of items and knapsack capacity.

Leave a Comment