Solution: 0/1 Knapsack DP
function fruitJar(capacity, fruits) {
// fruits = [{value, weight}, ...]
const n = fruits.length;
// dp[i][w] = max value using first i fruits with capacity w
const dp = Array(n + 1).fill(null)
.map(() => Array(capacity + 1).fill(0));
// Build dp table
for (let i = 1; i <= n; i++) {
const {value, weight} = fruits[i - 1];
for (let w = 0; w <= capacity; w++) {
// Don't take this fruit
dp[i][w] = dp[i - 1][w];
// Take this fruit (if it fits)
if (weight <= w) {
dp[i][w] = Math.max(
dp[i][w],
value + dp[i - 1][w - weight]
);
}
}
}
return dp[n][capacity];
}
// Test
const fruits = [
{value: 60, weight: 10},
{value: 100, weight: 20},
{value: 120, weight: 30}
];
console.log(fruitJar(50, fruits)); // 220 (fruits 2 and 3)
Space Optimized: 1D DP
function fruitJarOptimized(capacity, fruits) {
const n = fruits.length;
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
const {value, weight} = fruits[i];
// Iterate backwards to avoid overwriting
for (let w = capacity; w >= weight; w--) {
dp[w] = Math.max(
dp[w],
value + dp[w - weight]
);
}
}
return dp[capacity];
}
console.log(fruitJarOptimized(50, fruits)); // 220
Unbounded Knapsack (Unlimited Items)
function fruitJarUnbounded(capacity, fruits) {
const dp = Array(capacity + 1).fill(0);
for (let w = 1; w <= capacity; w++) {
for (const {value, weight} of fruits) {
if (weight <= w) {
// Can take this fruit again
dp[w] = Math.max(
dp[w],
value + dp[w - weight]
);
}
}
}
return dp[capacity];
}
// Test with same fruits
console.log(fruitJarUnbounded(50, fruits)); // 300 (5x fruit 1)
With Item Tracking
If you need to know which items were selected:
function fruitJarWithItems(capacity, fruits) {
const n = fruits.length;
const dp = Array(n + 1).fill(null)
.map(() => Array(capacity + 1).fill(0));
// Build dp table
for (let i = 1; i <= n; i++) {
const {value, weight} = fruits[i - 1];
for (let w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w];
if (weight <= w) {
dp[i][w] = Math.max(
dp[i][w],
value + dp[i - 1][w - weight]
);
}
}
}
// Backtrack to find items
const selected = [];
let i = n, w = capacity;
while (i > 0 && w > 0) {
// Was this item taken?
if (dp[i][w] !== dp[i - 1][w]) {
selected.push(i - 1); // 0-indexed
w -= fruits[i - 1].weight;
}
i--;
}
return {
maxValue: dp[n][capacity],
items: selected.reverse()
};
}
const result = fruitJarWithItems(50, fruits);
console.log("Max value:", result.maxValue); // 220
console.log("Items:", result.items); // [1, 2]
console.log("Weights:", result.items.map(i => fruits[i].weight)); // [20, 30]
Step-by-Step Example
Fruits: [{value: 60, weight: 10}, {value: 100, weight: 20}], capacity: 30
dp table:
w=0 10 20 30
i=0 0 0 0 0
i=1 0 60 60 60 (can take fruit 1)
i=2 0 60 100 160 (can take fruit 2, or both)
At dp[2][30]:
Don't take fruit 2: dp[1][30] = 60
Take fruit 2: 100 + dp[1][30-20] = 100 + 60 = 160 ✓
Answer: 160 (take both fruits)
Complexity Analysis
| Version |
Time |
Space |
| 2D DP |
O(n × capacity) |
O(n × capacity) |
| 1D DP optimized |
O(n × capacity) |
O(capacity) |
| Unbounded |
O(n × capacity) |
O(capacity) |
Common Mistakes
- Using greedy: Doesn't guarantee optimal for 0/1 knapsack
- Wrong iteration order: In 1D optimization, must go backwards
- Confusing bounded/unbounded: Different recurrences
- Integer overflow: Check if values/weights can overflow
Variations
Fractional knapsack: Can take fractions of items → Greedy works, sort by value/weight ratio
Multiple constraints: e.g., weight AND volume → Add another dimension to DP
Exact capacity: Must fill exactly → Initialize dp differently
Follow-Up Questions
Q: Can items be taken fractionally?
A: Then greedy works - sort by value/weight and take in order
Q: What if we have multiple knapsacks?
A: Multiple knapsack problem - more complex, might use greedy approximation
Q: Time complexity too slow?
A: Pseudo-polynomial (depends on capacity). If capacity is huge, might need approximation algorithms
Related Problems
