0/1 Knapsack
Updated
Problem statement
You have n items. Item i has a weight weights[i] and a value values[i]. You also have a bag that can hold a total weight of at most capacity.
Choose some of the items to put in the bag. Each item can be chosen at most once, and the total weight of the chosen items must be at most capacity.
Return the largest total value you can get. Choosing no items is allowed and gives a total value of 0.
Function
maxKnapsackValue(weights: int[], values: int[], capacity: int) → intExamples
Example 1
weights = [1,3,4,5]values = [1,4,5,7]capacity = 7return = 9Choose the items with weights 3 and 4. Their total weight is 3 + 4 = 7, and their total value is 4 + 5 = 9.
The item with weight 5 has the best value for its weight, but after taking it only 2 units of weight are left. Then only the weight-1 item fits, for a total value of 7 + 1 = 8. No other choice beats 9.
Example 2
weights = [4,6]values = [10,20]capacity = 3return = 0Both items weigh more than capacity = 3. No item fits, so the answer is 0.
Example 3
weights = [2,3]values = [3,4]capacity = 4return = 4Both items together weigh 5, which is more than 4. The weight-3 item alone gives 4, which beats 3 from the weight-2 item alone. Taking the weight-2 item twice would give 6, but each item can be chosen only once.
Constraints
1 <= weights.length <= 100values.length == weights.length1 <= weights[i] <= 10000 <= values[i] <= 100000 <= capacity <= 10000
More Confluent interview questions
- Count Combinations Using Weights One Through KOA · Seen Oct 2026
- Sum Symmetric Pairwise RemaindersOA · Seen Oct 2026
- Reach Target BalanceOA · Seen Mar 2026
- Tail N LinesOA · Seen Mar 2026
- Implement tail -nPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sudoku Board ValidationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sudoku Puzzle SolverPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Match a Variadic Function SignaturePHONE SCREEN · Seen Oct 2026
- Sequential Phrase Search Across DocumentsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Bounded Combination Sum with Signed CandidatesONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Minimum Cost to Tile a Strip with Widths 1, 2, and 3Infosys · OAInfosys interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Subarray SumStraive · OA
- Longest Increasing Price SubsequenceOpenAI · OAOpenAI interview questions
- Lowest-Cost Shirt Color ScheduleElevenLabs · OAElevenLabs interview questions
- Maximum Game Board ScoreJP Morgan Chase · OAJP Morgan Chase interview questions
- API Bandwidth AllocationArista Networks · OAArista Networks interview questions
- Maximum Points by Deleting ElementsIBM · OAIBM interview questions
- House RobberWalmart · OAWalmart interview questions
- Three-Resource 0/1 KnapsackMorgan Stanley · OAMorgan Stanley interview questions
Confluent interview experiences
- Confluent Older Concurrency Rounds: 12 Experiences (Part 2 of 2)
- Confluent Concurrency Interviews: 28 Experiences (Part 1 of 2)
- Confluent SWE OA, Coding and Design Interviews: 19 Experiences
- Confluent File Manipulation Round (tail -n): 19 Experiences
- Confluent Coding and System Design Questions: 33 Questions