1.knapsack01

0/1 Knapsack Problem (Memoized Approach in Java) What is the 0/1 Knapsack Problem?

The 0/1 Knapsack problem is a classic dynamic programming problem where:

You have N items, each with a weight and value. A knapsack has a maximum weight limit W. Each item can be either included (1) or not included (0) (i.e., no fractions allowed). Objective: Maximize the total value while ensuring the total weight does not exceed W.

Memoized (Top-Down) Approach Why Use Memoization?

The recursive approach leads to overlapping subproblems, causing repeated calculations. Memoization stores previously computed results in a cache (dp array), reducing redundant calculations. Time Complexity: O ( N × W ) O(N×W) Space Complexity: O ( N × W ) O(N×W) (for the dp array and recursion stack)

import java.util.Arrays;

public class Knapsack01 { // Memoization table static int[][] dp;

public static int knapsack(int W, int[] wt, int[] val, int n) {
    // Initialize memoization table with -1
    dp = new int[n + 1][W + 1];
    for (int[] row : dp) {
        Arrays.fill(row, -1);
    }
    return knapsackMemo(W, wt, val, n);
}

private static int knapsackMemo(int W, int[] wt, int[] val, int n) {
    // Base condition: If no items left or capacity is 0
    if (n == 0 || W == 0) {
        return 0;
    }

    // If the result is already computed, return it
    if (dp[n][W] != -1) {
        return dp[n][W];
    }

    // If the weight of the nth item is greater than capacity, exclude it
    if (wt[n - 1] > W) {
        dp[n][W] = knapsackMemo(W, wt, val, n - 1);
    } else {
        // Either exclude or include the item and take max value
        dp[n][W] = Math.max(
            knapsackMemo(W, wt, val, n - 1), 
            val[n - 1] + knapsackMemo(W - wt[n - 1], wt, val, n - 1)
        );
    }
    return dp[n][W];
}

public static void main(String[] args) {
    int[] val = {60, 100, 120};
    int[] wt = {10, 20, 30};
    int W = 50;
    int n = val.length;

    System.out.println("Maximum Value: " + knapsack(W, wt, val, n));
}

}