495. Which Items Went In

Each item has a weight and a value and may be used at most once. The bag holds at most C total weight. Report the largest total value AND which items achieve it.

Several selections can tie on value, so the answer has to be pinned. Report the LEXICOGRAPHICALLY SMALLEST list of 1-based indices, in increasing order, among all selections achieving the maximum. Comparing two sorted lists means comparing their first differing position, and a list that is a prefix of another is the smaller one.

items (w=4 v=10) (w=2 v=5) (w=2 v=5), C = 4 -> 10, items 1

Both {1} and {2,3} reach value 10. [1] is lexicographically smaller than [2,3] because 1 < 2, so the answer is item 1 alone.

## Why a tie-break has to exist

The judge compares output bytes. Without a rule, two correct algorithms print different correct answers and one of them is marked wrong. Whenever a problem asks WHICH rather than HOW MANY or HOW MUCH, the statement owes you a tie-break, and if it does not give one the problem is broken.

Worth noticing as a reader, and worth supplying as an author.

## The usual reconstruction, and why it is not enough

The standard method fills the ordinary dp table forward, then walks BACKWARD from dp[n][C]: if dp[i][c] differs from dp[i-1][c] then item i was taken.

That recovers some optimal selection. It gives no control over which one, and on the sample it returns {2,3}, because walking backward prefers the later items.

## Getting the lexicographically smallest

Build a SUFFIX table instead:

best[i][c] = the largest value obtainable from items i..n using capacity c

filled from i = n downward. Then sweep items FORWARD and take each one whenever taking it keeps the optimum reachable:

c = C for i in 1..n: if c >= w[i] and best[i+1][c - w[i]] + v[i] == best[i][c]: take item i; c -= w[i]

## Why that gives the smallest list

The first index of the answer should be as small as possible, because comparing sorted lists compares first elements first. So item 1 belongs in the answer if ANY optimal selection contains it, and the test best[2][C - w1] + v1 == best[1][C] says exactly that.

Having committed to item 1, the same reasoning applies to the remaining items with the reduced capacity, which is a smaller instance of the identical question. So the greedy is correct by induction, and no comparison of candidate lists is ever needed.

The direction of the table is what makes it work. A prefix table cannot answer "is item i in some optimal selection of the WHOLE instance", because it knows nothing about what comes after.

## Output shape

Print the value, then the count, then the indices, all space separated on one line. When nothing is taken, that is 0 0 and nothing follows, which avoids an empty line that whitespace-splitting readers would lose.

(w=5 v=9) with C = 4 answers 0 0: nothing fits, and the empty selection is the optimum.

Constraints - `1 ≤ n ≤ 500` - `0 ≤ C ≤ 2000` - `1 ≤ weight ≤ 2000` - `1 ≤ value ≤ 1000000`