55. DP Example 3: Knapsack Problem (0/1 Introduction)

The 0/1 Knapsack Problem

You have a knapsack (bag) with a maximum weight capacity W. You have a set of N items, each with a specific weight and a specific value. You must decide, for each item, whether to take it (1) or leave it (0). The goal is to maximize the total value without exceeding the capacity W.

Why DP?

This problem has both Optimal Substructure (the best solution for a capacity w relies on the best solution for capacities less than w) and Overlapping Subproblems.

DP State Definition

We define a 2D DP table: DP[i][w] = maximum value achievable using the first i items with a knapsack capacity of w.

For each item i and capacity w, we decide:

1. Don't include item i: DP[i-1][w]
2. Include item i: value[i] + DP[i-1][w - weight[i]]

We choose the maximum of these two options. This iterative filling of the DP table solves the complex problem efficiently.