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.