Solve and extend the Knapsack problem

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.

0/1 Knapsack: Max Value and Optimal Item Set

You are given n items, where item i has integer weights[i] and values[i], and a knapsack capacity W. Each item may be taken at most once (0/1 knapsack).

Return a tuple (max_value, chosen) where:

• max_value is the maximum total value of any subset of items whose total weight does not exceed W.
• chosen is a list of the selected item indices (the reconstructed optimal set), sorted in ascending order. If several optimal sets exist, return the one produced by the standard backward reconstruction described below.

Core idea (O(nW) time, O(W) space). Maintain a 1D DP array dp of length W + 1, where dp[c] is the best achievable value using a capacity of c. Process items one at a time; for each item iterate the capacity from W down to weights[i] (descending so each item is used at most once) and apply dp[c] = max(dp[c], dp[c - weights[i]] + values[i]). The answer value is dp[W].

Reconstructing choices from compressed state. The rolling 1D dp alone forgets which items were taken. To recover one optimal set, record, for each item i and capacity c, whether taking item i strictly improved dp[c] at the moment it was processed (a keep[i][c] flag). After filling the table, walk items from last to first: at the current remaining capacity c, if keep[i][c] is set, add i to the chosen set and subtract weights[i] from c. Finally sort the chosen indices. (Recording keep is O(nW) extra space; an alternative that preserves O(W) working space is to store only the rolling dp and re-derive choices via a second pass or by keeping dp snapshots — both are acceptable, the keep table is shown here for clarity.)

Variants (discussion).

• Unbounded knapsack (each item usable unlimited times): iterate the inner capacity loop ascending (weights[i]..W) instead of descending, so the same item can be reused within one pass. Time O(nW), space O(W).
• Bounded knapsack (item i usable up to c_i times): the naive approach loops each copy (O(W * sum(c_i))). The efficient approach uses binary (power-of-two) decomposition of each multiplicity into log2(c_i) virtual items and then runs 0/1 knapsack, giving O(W * sum(log c_i)) time; a monotonic-deque optimization achieves O(nW).

Return the tuple for the 0/1 case.

Constraints

• 0 <= n <= 1000 (n == len(weights) == len(values))
• 0 <= W <= 10000
• 1 <= weights[i] <= W (when n > 0); 0 <= values[i] <= 10^6
• Each item may be used at most once (0/1 knapsack)
• If multiple optimal subsets exist, return the one from the standard backward reconstruction (indices sorted ascending)

Examples

Example 1

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

Explanation: Items 1 (w=3,v=4) and 2 (w=4,v=5) fill weight 7 exactly for value 9 — better than item 3 alone (v=7) or items 0+3 (w=6,v=8).

Example 2

Input: ([2, 3, 4, 5], [3, 4, 5, 6], 5)
Output: (7, [0, 1])

Explanation: Items 0 (w=2,v=3) and 1 (w=3,v=4) use weight 5 for value 7, beating any single item that fits (max single value at w<=5 is 6).

Hints

1. Use a 1D dp array of size W+1 and iterate the capacity from W down to weights[i] so each item is counted at most once. Iterating ascending instead would turn it into the unbounded variant.
2. The rolling 1D dp forgets which items were taken. Record a keep[i][c] flag whenever taking item i strictly improves dp[c], then reconstruct by walking items backward from capacity W.
3. Edge cases: empty item list, an item heavier than W (never fits), and W == 0 should all return value 0 and an empty chosen set.