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.