Knapsack Problems
The 0/1 knapsack problem is a classic DP problem: given weights and values of n items, and a capacity W, maximize the total value without exceeding capacity, where each item can be taken at most once.
Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) if weight[i] ≤ w, else dp[i-1][w].
Java implementation (tabulation):
public static int knapsack01(int[] wt, int[] val, int W) {
int n = wt.length;
int[][] dp = new int[n+1][W+1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (wt[i-1] <= w) {
dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1]);
} else {
dp[i][w] = dp[i-1][w];
}
}
}
return dp[n][W];
}
Variants:
- Fractional knapsack – greedy works.
- Unbounded knapsack – items can be taken multiple times (similar to coin change).
Two Minute Drill
- 0/1 knapsack: each item taken once. DP O(nW).
- State: dp[i][w] = max value using first i items with capacity w.
- Transition: take or skip item.
- Space can be optimized to 1D array (iterate w backwards).
Need more clarification?
Drop us an email at career@quipoinfotech.com