Unbounded 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: Unbounded Knapsack * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Unbounded Knapsack * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given weights and values of N items and a Capacity C. * Maximize total value. * Constraint: Items can be chosen UNLIMITED times (Repetition allowed). * * --------------------- * 2. Logical Breakdown * --------------------- * Let dp[w] be the max value for capacity 'w'. * * Recurrence: * dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) for all items i. * * 1D Array Logic (Forward Iteration): * Unlike 0-1 Knapsack, we iterate FORWARDS (from 0 to C). * When we compute dp[w] using item 'i', we look up dp[w - weight[i]]. * Since we are iterating forward, dp[w - weight[i]] already considers item 'i'. * This effectively allows us to add item 'i' again to a sack that already contains it. * * --------------------- * 3. Complexity * --------------------- * Time Complexity: O(N * C) * Space Complexity: O(C) * * ============================================================================================ */ public class UnboundedKnapsack { public int solve(int A) { // TODO: Implement solution return 0; }
public int solveUnboundedKnapsack(int[] val, int[] wt, int i) {
return 1;
}
}