Zero One Knapsack
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.dynamic_programming;
import java.util.*;
/ * Problem: Zero One Knapsack * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: 0-1 Knapsack * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given two integer arrays 'values' and 'weights' of size N, and an integer C (Capacity). * Maximize the total value in the knapsack such that the total weight <= C. * Constraint: Each item can be selected AT MOST ONCE (0 or 1 time). * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let dp[i][w] be the maximum value we can obtain using a subset of the first 'i' items * with a total weight capacity limit of 'w'. * * Recurrence Relation: * For the i-th item (with value v and weight wt), we have two choices: * * 1. Exclude Item i: * Value = dp[i-1][w] * * 2. Include Item i (Only if wt <= w): * Value = v + dp[i-1][w - wt] * * Combine: * dp[i][w] = max(dp[i-1][w], (wt <= w ? v + dp[i-1][w - wt] : 0)) * * Space Optimization (1D Array): * Notice that to calculate state for 'i', we only need state for 'i-1'. * We can reduce space to O(C). * CRITICAL: When iterating with a 1D array for 0-1 Knapsack, we must iterate BACKWARDS * (from C down to wt). * Why? To ensure that when we calculate dp[w], the value at dp[w-wt] represents the state * from the previous iteration (i-1), effectively ensuring we don't use the same item twice. * * --------------------- * 3. Constraints & Complexity * --------------------- * Time Complexity: O(N * C) * Space Complexity: O(C) (Optimized) * * ============================================================================================ */ public class ZeroOneKnapsack { public int solve(int A) { // TODO: Implement solution return 0; }
public int solve01Knapsack(int[] val, int[] wt, int i) {
return 1;
}
}