Class Knapsack

java/Dynamic Programming/Knapsack.java:1–26

public class Knapsack {
    public int knapsack(int cap, int[] weights, int[] values) {
        int n = values.length;
        // Base case: Set the first column and last row to 0 by
        // initializing the entire DP table to 0.
        int[][] dp = new int[n + 1][cap + 1];

        // Populate the DP table.
        for (int i = n - 1; i >= 0; i--) {
            for (int c = 1; c < cap + 1; c++) {
                // If the item 'i' fits in the current knapsack capacity,
                // the maximum value at 'dp[i][c]' is the largest of either:
                // 1. The maximum value if we include item 'i'.
                // 2. The maximum value if we exclude item 'i'.
                if (weights[i] <= c) {
                    dp[i][c] = Math.max(values[i] + dp[i + 1][c - weights[i]], dp[i + 1][c]);
                }
                // If it doesn't fit, we have to exclude it.
                else {
                    dp[i][c] = dp[i + 1][c];
                }
            }
        }
        return dp[0][cap];
    }
}