A knapsack has a maximum capacity C and there are n items each with weight w[i] and value v[i]. Maximize the knapsack value without exceeding capacity.

This is a classic dynamic programming problem, often referred to as the 0/1 Knapsack problem. The goal is to select items to maximize total value without exceeding a given weight capacity. We can solve this using a DP table where dp[i][c] represents the maximum value achievable using the first i items with a capacity of c. The recurrence relation is: dp[i][c] = max(dp[i-1][c], values[i-1] + dp[i-1][c - weight[i-1]]) if c >= weight[i-1], otherwise dp[i][c] = dp[i-1][c]. The time complexity is O(nC) and the space complexity is O(nC), where n is the number of items and C is the capacity. This space complexity can be optimized to O(C) by using only two rows or even a single row of the DP table.