Explain the 0/1 Knapsack problem and its DP solution.

Given items with weights and values, maximize total value that fits in a knapsack of capacity W. Each item is either included or excluded (0/1). DP solution uses 2D table dp[i][w] = max value using first i items with capacity w. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]). Time and space are O(nW). Space can be optimized to O(W) using 1D array processed right-to-left.