0/1 Knapsack
Custom BASA DSA problem: 0/1 Knapsack.
You are given n items. Every item has a weight and a value, and you have a knapsack with a maximum weight capacity. Choose a subset of the items that maximizes the total value while the total weight stays inside the capacity.
Each item is taken entirely or not at all. An item may be selected at most once, and you can never take a fraction of an item.
The total weight of the selected items must not exceed
capacity.Unused capacity is allowed, and selecting no items is allowed.
The goal is the maximum total value, not the maximum total weight.
Write knapsack(weights, values, capacity) and return two things:
The maximum total value that fits in the knapsack.
The indices of the items you selected, in increasing order.
Return shape. Python returns the tuple (maxValue, selectedIndices) and TypeScript returns the array [maxValue, selectedIndices]. The runner reads that pair as [maxValue, selectedIndices].
Ties. Different subsets can be worth exactly the same maximum value. Any of them is accepted: the runner checks that your indices are a valid selection and that their total value equals the maximum value for that input.
Signature. BASA DSA starts every Python exercise inside class Solution, so the method is def knapsack(self, weights, values, capacity). The TypeScript starter is a plain function knapsack(weights, values, capacity).
Your requested scenario. With weights = [3, 4, 1, 3], values = [3, 5, 0.5, 3], and capacity = 6, the maximum value is 6, reached by items 0 and 3, which weigh 3 + 3 = 6.
Example 1 · Half-point values
weights = [3,4,1,3]
values = [3,5,0.5,3]
capacity = 6[6,[0,3]]Explanation
Items 0 and 3 weigh 3 each and are worth 3 each, so together they fill the capacity exactly and are worth 6. The remaining options are worth less: items 0 and 2 weigh 4 and are worth 3.5, items 1 and 2 weigh 5 and are worth 5.5, and item 1 alone is worth 5. Item 0 plus item 1 would weigh 7, which does not fit.
Example 2 · One item or two
weights = [1,3,4]
values = [15,20,30]
capacity = 4[35,[0,1]]Explanation
Item 2 alone is worth 30 and fills the knapsack. Items 0 and 1 weigh 1 + 3 = 4 and are worth 15 + 20 = 35, which is better. Item 1 alone is worth 20 and items 0 and 2 weigh 5, which does not fit. The maximum is 35.
Example 3 · Two optimal subsets
weights = [2,3]
values = [5,5]
capacity = 3[5,[0]]Explanation
Either item alone fits and is worth 5, so both subsets tie at the same maximum value of 5. Item 0 is reported because it is the earlier index; returning item 1 is equally correct.
Constraints
- 0 <= n <= 60, where n is the number of items.
- 1 <= weights[i] <= 500 for every item.
- 0 <= values[i] <= 500 for every item. Values may be fractional.
- 0 <= capacity <= 500.
- weights and values always have the same length.
knapsackArguments: json, json, jsonRun: 3 examples; Submit: 40 cases, on your device. 40 independently authored deterministic cases, including 3 Run examples. Submit checks empty item lists, zero capacity, fractional values, zero-value items, tied optima, a greedy trap, twenty-item and sixty-item inputs, and 15 seeded mixed traces. These are inspectable local practice cases.
[3,4,1,3][3,5,0.5,3]6