Optimize 0/1 to bounded knapsack DP

Q: Optimize 0/1 to bounded knapsack DP

This is a Coding & Algorithms interview question from Google for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Solve the 0/1 knapsack problem: given arrays weight[i], value[i] for i=0..n-1 and capacity W, return the maximum value and reconstruct one optimal set of item indices. Provide both O(nW) time/O(nW) space and O(nW) time/O(W) space solutions. Next, extend your solution to the bounded knapsack variant where each item i has a limited count count[i]. Implement an O(nW) approach using binary decomposition of counts (or another efficient method), and explain the complexity and memory trade-offs. Dry-run both variants on: weight=[2,3,4], value=[4,5,10], W=7 (0/1 case), then count=[3,1,2] (bounded case).

Optimize 0/1 to bounded knapsack DP

Comments (0)