Solve and extend the Knapsack problem
BitGoSoftware Engineer · Technical ScreenLast updated
This question evaluates a candidate's understanding of dynamic programming for optimization problems, specifically the 0/1 knapsack formulation, space-optimized DP and the ability to reconstruct a chosen item set from compressed state.
You are given n items, each with an integer weight and value, and a knapsack capacity W. Implement 0/1 Knapsack to return the maximum total value and also reconstruct one optimal set of item indices. Provide an O(nW) time, O(W) space dynamic programming solution and explain how to reconstruct choices from the compressed state. Then outline how to adapt the solution to unbounded and bounded knapsack variants and analyze time and space complexity.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.