Zero-One Knapsack
Updated
Problem statement
You have a bag that can carry a total weight of at most capacity, and a list of items. Item i weighs weights[i] and is worth values[i]. Each item can be put in the bag at most once.
Choose some of the items so that their total weight is at most capacity. Return the largest total value you can get. Choosing no items gives 0.
Function
knapsack(weights: int[], values: int[], capacity: int) → intExamples
Example 1
weights = [2,3,4,5]values = [3,4,5,6]capacity = 5return = 7Several choices fit in a bag of capacity 5. Items 0 and 1 weigh 2 + 3 = 5 and are worth 3 + 4 = 7. Item 3 alone weighs 5 and is worth 6. Item 2 alone is worth 5. The best is 7.
Example 2
weights = [3,2,2]values = [5,3,3]capacity = 4return = 6Item 0 is worth the most per unit of weight (5 for 3), but it leaves only 1 unit of room, so nothing else fits and the total is 5. Items 1 and 2 weigh 2 + 2 = 4 and are worth 3 + 3 = 6. The best is 6.
Example 3
weights = [5,6]values = [10,20]capacity = 4return = 0Both items are heavier than the capacity 4, so none can be taken. The best is 0.
Example 4
weights = [2]values = [7]capacity = 6return = 7The only item can be taken once, so the total is 7, even though three copies would fit by weight.
Constraints
1 <= weights.length <= 100values.length == weights.length1 <= weights[i] <= 1001 <= values[i] <= 10001 <= capacity <= 1000
More Bloomberg LP Phone Screen questions
- N-ary Index-Path Encoder and DecoderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Trapping Rain WaterPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Word SearchOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Fewest Coins CombinationPHONE SCREEN · Seen Nov 2026
- Recommend Films from Viewers Who Watched Everything You DidPHONE SCREEN · Seen Nov 2026
- Track New Values in Sorted OrderPHONE SCREEN · Seen Nov 2026
- Design Browser HistoryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Sparse Vector and Matrix OperationsPHONE SCREEN · Seen Oct 2026
- Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Maximum Subarray Sum with One DeletionServiceNow · PHONE SCREENServiceNow interview questions
- Maximum Product of a Contiguous SubarrayLinkedIn · PHONE SCREENLinkedIn interview questions
- Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
- Jump GamePaytm · PHONE SCREENPaytm interview questions
- Query Words Within K PositionsPalantir · PHONE SCREENPalantir interview questions
- House RobberVisa · PHONE SCREENVisa interview questions
- Best Improvement Period of at Least K IntervalsAmazon · PHONE SCREEN
- Longest Increasing SubsequenceAngel One · PHONE SCREEN
- Match Shops and BuyersGoogle · PHONE SCREENGoogle interview questions
- Minimum Cost for a Target WeightPace Stock Broking Services · PHONE SCREEN
Interview reports that mention this question
Bloomberg LP interview experiences
- Bloomberg AI-Assisted Coding Round, All Levels: 14 Experiences
- Bloomberg SWE Intern Interview Questions: 68 Questions
- Bloomberg Interview Questions, Level Not Reported: 65 Questions
- Bloomberg Experienced SWE Interviews: 167 Questions (Part 1 of 2)
- Bloomberg New Grad Coding Questions: 121 Questions (Part 2 of 2)