Knapsack (Recovering Items)

Problem:
Given a knapsack with capacity n and m items, where each item has a value and weight, determine the maximum value that can be placed in the knapsack.

In addition to the maximum value, return which items were selected.

This is the classic Knapsack dynamic programming problem with backtracking.

💡 Approach

We define a DP table:

t[i][j] = maximum value using the first i items with capacity j

Each item gives us two choices.

1️⃣ Skip the item

Do not include item i.

t[i-1][j]

2️⃣ Take the item

If the weight allows, include item i.

t[i-1][j - weight] + value

So the recurrence is:

t[i][j] = max(t[i-1][j], t[i-1][j-weight] + value)

Why this works

At every item, we choose between:

• skipping the item
• taking the item (if it fits)

The DP table builds optimal solutions for all prefixes of items and capacities.

🔍 Recovering the Selected Items

After filling the table, we backtrack from t[m][n]:

• If the value came from including the item, we add it to our solution
• Then reduce the remaining capacity

This lets us reconstruct the actual set of chosen items.

import sys

for line in sys.stdin:
    line = line.strip()
    if not line:
        continue

    # capacity n, number of items m
    n, m = map(int, line.split())

    # DP table
    t = [[0] * (n + 1) for _ in range(m + 1)]

    items = []

    # build DP table
    for i in range(1, m + 1):
        value, weight = map(int, sys.stdin.readline().split())
        items.append((value, weight))

        for j in range(1, n + 1):
            if weight <= j:
                t[i][j] = max(t[i-1][j], t[i-1][j-weight] + value)
            else:
                t[i][j] = t[i-1][j]

    # backtrack to find selected items
    selected_items = []
    j = n

    for i in range(m, 0, -1):
        value, weight = items[i-1]

        if j >= weight and t[i][j] == t[i-1][j-weight] + value:
            selected_items.append(i-1)
            j -= weight

    selected_items.reverse()

    # output
    print(len(selected_items))
    print(" ".join(map(str, selected_items)))