LOG_ENTRY // Dynamic Programming

Space-OptimizedDP:
The0/1KnapsackProblem

Apr 2026 12 min read

The Knapsack problem is the gateway to understanding combinatorial optimization. While the 2D matrix is intuitive, the real engineering flex is the space-optimized 1D array.

SOURCE_MANIFEST

class Solution {
    static int knapsack(int[] wt, int[] val, int n, int W) {
        // Space optimized: single row array
        int[] prev = new int[W + 1];

        // Base case: first item
        for (int i = wt[0]; i <= W; i++) {
            prev[i] = val[0];
        }

        for (int ind = 1; ind < n; ind++) {
            for (int cap = W; cap >= 0; cap--) {
                int notTake = prev[cap];
                int take = Integer.MIN_VALUE;
                if (wt[ind] <= cap) {
                    take = val[ind] + prev[cap - wt[ind]];
                }
                prev[cap] = Math.max(take, notTake);
            }
        }
        return prev[W];
    }
}