Overview

This is a classic “0-1 Knapsack Problem.” We use dynamic programming (DP) to find the combination of treasures that maximizes the total value while satisfying the weight constraint.

Analysis

Naive Approach and Its Problems

Since each treasure has two choices—”include” or “exclude”—trying all combinations results in \(2^N\) possibilities. When \(N = 100\), \(2^{100}\) is an astronomical number, making it impossible to finish the computation in time (TLE).

Key Insights

This problem has the properties of optimal substructure and overlapping subproblems. - When considering “the maximum value when selecting from the first \(i\) treasures with total weight at most \(j\),” we can break it down into two cases: whether to include treasure \(i\) or not - The same subproblems appear multiple times

This is a sign that the problem can be solved efficiently with dynamic programming.

State Definition

\(dp[j]\) = the maximum value when selecting treasures such that the total weight is at most \(j\)

Algorithm

DP Transition

For each treasure \((T_i, S_i)\), consider a knapsack of weight \(j\): - If we don’t include treasure \(i\): \(dp[j]\) remains unchanged - If we include treasure \(i\): \(dp[j-T_i] + S_i\) (maximum value with space reserved for treasure \(i\) + value of treasure \(i\))

We take the larger of these two: $\(dp[j] = \max(dp[j], dp[j - T_i] + S_i)\)$

Concrete Example

For \(N=3, M=5\) with treasures \((T, S) = (2, 3), (3, 4), (2, 2)\):

Treasure	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]
Initial	0	0	0	0	0	0
(2,3)	0	0	3	3	3	3
(3,4)	0	0	3	4	4	7
(2,2)	0	0	3	4	5	7

The answer is \(dp[5] = 7\) (selecting treasure 1 and treasure 2)

Why Update in Reverse Order?

Important: Each treasure can only be used once. If we update in forward order (from \(j = T_i\) to \(M\)), we might use the same treasure multiple times.

By updating in reverse order (from \(j = M\) to \(T_i\)), we guarantee that the value \(dp[j-T_i]\) refers to a state where “treasure \(i\) has not been used yet.”

Complexity

• Time Complexity: \(O(N \times M)\)
  • For each treasure, we loop at most \(M\) times
  • With \(N = 100, M = 10^5\), approximately \(10^7\) operations, which is fast enough
• Space Complexity: \(O(M)\)
  • Only uses a 1-dimensional array \(dp\)

Implementation Notes

1. Save space with 1D DP: While a 2D array \(dp[i][j]\) approach is also possible, a 1D array is sufficient
2. Reverse loop is essential: Using range(M, T - 1, -1) to update from \(M\) down to \(T\) guarantees each treasure is used only once
3. Initialization: Start with dp[0] = 0 (value is 0 when nothing is included), and initialize all others to 0 as well
4. Output the answer: \(dp[M]\) is “the maximum value achievable with weight at most \(M\)”

Source Code

def solve():
    N, M = map(int, input().split())
    items = []
    for _ in range(N):
        T, S = map(int, input().split())
        items.append((T, S))
    
    # dp[j] = maximum value when weight is exactly j or less
    # Save space with 1D DP
    dp = [0] * (M + 1)
    
    for T, S in items:
        # Update in reverse order to guarantee each item is used only once
        for j in range(M, T - 1, -1):
            dp[j] = max(dp[j], dp[j - T] + S)
    
    print(dp[M])

solve()

---

This editorial was generated by claude4.5opus.