P13 · 2 seconds · 256 MB
0/1 Knapsack
You have `n` items. Item `i` has weight `weights[i]` and value `values[i]`. You may take each item at most once. Return the maximum total value of a subset whose total weight is at most `cap`. Leftover capacity is allowed. If `n = 0` or `cap = 0`, the answer is 0.
function knapsack(weights, values, cap) → number
CONSTRAINTS
- 0 ≤ n ≤ 100
- weights.length === values.length === n
- 1 ≤ weights[i], values[i] ≤ 10³ (when n > 0)
- 0 ≤ cap ≤ 10³
Input: weights = [2, 3, 4, 5], values = [3, 4, 5, 6], cap = 8
Output: 10
Items with weights 3 and 5 (values 4 and 6). Total weight 8, value 10.
Input: weights = [1, 2, 3], values = [6, 10, 12], cap = 5
Output: 22
Weights 2 and 3, values 10 and 12.
Input: weights = [1], values = [1], cap = 0
Output: 0
1
2
3
4
5
6
7
8
Arena judges JavaScript in a Web Worker (1s wall-clock, then TLE). Samples are public; submit runs hidden tests too. C++/Python is a later swarm package.