Knapsack family — 0/1 partition, unbounded, min cost to fill a bag, min removals for range

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.