One Constraint to Two

Classic knapsack has one constraint: weight capacity. But real problems often have multiple constraints. A backpacker might care about both weight and volume. A project manager about both budget and time. Multi-dimensional knapsack tracks multiple constraints in dp.

Instead of $dp[w]$, you use $dp[w_1][w_2]$ for two constraints, or $dp[w_1][w_2][w_3]$ for three. The next problem has two constraints: count of zeros and count of ones. Let's see how to handle it.