Quick Overview

This question evaluates mastery of dynamic programming for knapsack problems, focusing on state formulation, space-time optimization, and reconstructing optimal item sets.

Optimize 0/1 to bounded knapsack DP

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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).

Quick Answer: This question evaluates mastery of dynamic programming for knapsack problems, focusing on state formulation, space-time optimization, and reconstructing optimal item sets.

0/1 Knapsack with Solution Reconstruction

You are given arrays `weight[i]` and `value[i]` for items `i = 0..n-1`, and a knapsack capacity `W`. Each item may be taken at most once. Return a pair `(max_value, chosen_indices)` where `max_value` is the maximum total value achievable without exceeding capacity `W`, and `chosen_indices` is one optimal set of selected item indices in ascending order. Provide the classic O(nW) time / O(nW) space dynamic program. The 2D table `dp[i][w]` (max value using the first `i` items at capacity `w`) is also what enables reconstruction: walk back from `dp[n][W]`, and whenever `dp[i][w] != dp[i-1][w]` item `i-1` was taken. A space-optimized O(W) variant exists for the value alone, but reconstructing the chosen set requires either the full 2D table or storing per-item decision bits. Dry run on `weight=[2,3,4]`, `value=[4,5,10]`, `W=7`: the optimum is value `15` taking items `{1, 2}` (weights 3+4=7).

Constraints

  • 0 <= n <= 1000
  • 0 <= W <= 10000
  • 0 <= weight[i], value[i]
  • len(weight) == len(value) == n
  • Each item may be selected at most once (0/1).

Examples

Input: ([2,3,4], [4,5,10], 7)

Expected Output: (15, [1, 2])

Explanation: Take items 1 (w3,v5) and 2 (w4,v10): total weight 7, value 15 — the headline dry-run case.

Input: ([1,2,3], [6,10,12], 5)

Expected Output: (22, [1, 2])

Explanation: Items 1 (w2,v10) + 2 (w3,v12) fill capacity 5 for value 22, beating item 0.

Hints

  1. Define dp[i][w] = best value using the first i items at capacity w. Transition: skip item i-1 (dp[i-1][w]) or take it if it fits (dp[i-1][w-weight[i-1]] + value[i-1]).
  2. To reconstruct, walk i from n down to 1: if dp[i][w] differs from dp[i-1][w], item i-1 was taken — subtract its weight from w and record the index.
  3. For O(W) space you can collapse to one row iterated w from W down to weight[i-1], but you lose the per-step history needed to reconstruct unless you save decision bits.

Bounded Knapsack via Binary Decomposition

Extend 0/1 knapsack to the bounded variant: item `i` has weight `weight[i]`, value `value[i]`, and may be taken at most `count[i]` times. Given capacity `W`, return the maximum total value. The efficient trick is binary decomposition of each item's count. Split `count[i]` into powers of two `1, 2, 4, ..., remainder`; each chunk becomes a single virtual 0/1 item with weight `weight[i]*chunk` and value `value[i]*chunk`. Any quantity from 0 to count[i] is representable by choosing a subset of these chunks, so the problem reduces to ordinary 0/1 knapsack over O(sum log count[i]) virtual items — solved with the standard O(W) rolling-array DP. Dry run on `weight=[2,3,4]`, `value=[4,5,10]`, `count=[3,1,2]`, `W=7`: the optimum is value `15` (one item 1 of weight 3 plus one item 2 of weight 4 = weight 7).

Constraints

  • 0 <= n <= 1000
  • 0 <= W <= 10000
  • 0 <= weight[i], value[i]
  • 0 <= count[i]
  • len(weight) == len(value) == len(count) == n

Examples

Input: ([2,3,4], [4,5,10], [3,1,2], 7)

Expected Output: 15

Explanation: Headline dry run: take one item 1 (w3,v5) + one item 2 (w4,v10) = weight 7, value 15. Using more copies of cheaper items can't beat it within capacity 7.

Input: ([2,3,4], [4,5,10], [1,1,1], 7)

Expected Output: 15

Explanation: All counts 1 — reduces to the 0/1 case, same optimum 15.

Hints

  1. Naively turning each item into count[i] separate 0/1 items works but is O(W * sum count[i]) — too slow when counts are large.
  2. Binary decomposition: 1 + 2 + 4 + ... + 2^(k-1) + r = count[i], and any 0..count[i] copies are reachable by picking a subset of these chunks. This drops the factor to sum log(count[i]).
  3. After decomposition it's plain 0/1 knapsack: one rolling array dp[w], iterate w from W down to chunk_weight so each chunk is used at most once.

Loading coding console...