Knapsack Problem

//Knapsack Problem (0/1) 

import java.util.*;

public class Knapsack01 {

    // Memo table to store results: dp[index][capacity]
    private static int[][] dp;

    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        dp = new int[n][capacity + 1];

        // Initialize dp with -1 (meaning not computed)
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }

        // Start recursion from index 0 and full capacity
        return helper(weights, values, capacity, 0);
    }

    // Recursive helper function
    private static int helper(int[] weights, int[] values, int capacity, int index) {
        // Base case: no more items or no capacity left
        if (index == weights.length || capacity == 0) {
            return 0;
        }

        // Return cached result if already computed
        if (dp[index][capacity] != -1) {
            return dp[index][capacity];
        }

        // Option 1: skip current item
        int skip = helper(weights, values, capacity, index + 1);

        int pick = 0;
        // Option 2: pick current item (if it fits)
        if (weights[index] <= capacity) {
            pick = values[index] + helper(weights, values, capacity - weights[index], index + 1);
        }

        // Store the max value obtained by picking or skipping
        dp[index][capacity] = Math.max(pick, skip);

        return dp[index][capacity];
    }

    // Driver code to test
    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {1, 4, 5, 7};
        int capacity = 7;

        int maxValue = knapsack(weights, values, capacity);
        System.out.println("Maximum value in knapsack = " + maxValue);
    }
}