Knapsack family — 0/1 partition, unbounded, min cost to fill a bag, min removals for range
Problem
Knapsack variations:
Partition Equal Subset Sum — can the array be split into two parts with equal sums? Unbounded knapsack — each item can be taken any number of times. Minimum cost to fill a bag of exactly W kg, where cost[i] is the price of an i kg packet (−1 means unavailable). Minimum removals so that max − min ≤ k.
Example 1
Input: partition [1, 5, 11, 5] Output: true
[1, 5, 5] and [11].
Example 2
Input: partition [1, 2, 3, 5] Output: false
Also asked as: Partition problem · Unbounded Knapsack (Repetition of items allowed) · Maximize The Cut Segments · Minimum removals from array to make max –min <= K
Test cases
Case 1
Input: [1,5,11,5] Expected: true
Case 2
Input: [1,2,3,5] Expected: false
Case 3
Input: [2,2] Expected: true
View solutionHide solution2 approaches
1. Partition problem (equal-subset-sum) — boolean subset-sum on total/2
Time O(n·sum)Space O(sum)
If the total is odd, impossible. Otherwise ask "is there a subset summing to total/2?" with the 1-D subset-sum DP.
function canPartition(nums) { const total = nums.reduce((s, v) => s + v, 0); if (total % 2) return false; const target = total / 2; const dp = new Array(target + 1).fill(false); dp[0] = true; for (const num of nums) for (let s = target; s >= num; s--) dp[s] = dp[s] || dp[s - num]; return dp[target];}2. Unbounded knapsack
Time O(n·W)Space O(W)
Same table as 0/1 but iterate the weight axis ASCENDING so an item can be reused. dp[w] = max(dp[w], dp[w−weight] + value).
function unboundedKnapsack(weights, values, W) { const dp = new Array(W + 1).fill(0); for (let w = 1; w <= W; w++) for (let i = 0; i < weights.length; i++) if (weights[i] <= w) dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]); return dp[W];}Min cost to fill weight W (costs may be −1 = unavailable): unbounded knapsack minimising cost. Min removals so max−min ≤ K: sort, then it becomes "keep the longest window with a[j]−a[i] ≤ K"; removals = n − that window length.