Priority Context Packing Under a Token Budget

1. Background Knowledge

This problem is a variant of the 0/1 Knapsack Problem, a classic dynamic programming challenge where you select a subset of items to maximize total value subject to a weight (or cost) constraint. In the standard formulation, each item can be taken at most once, and the goal is to find the optimal subset. Here, the "weight" is the token cost, and the "value" is the snippet's utility score.

A critical twist in this problem is the presence of pinned items. These are mandatory inclusions that must always appear in the final context window. Conceptually, you can treat pinned items as a fixed overhead: their total cost is subtracted from the available budget, and their total value is added to the final answer. If the pinned items alone exceed the budget, the remaining budget for optional items becomes zero (or negative, which effectively means no optional items can be added), but the pinned items are still included in the total value.

The remaining optional items form a standard 0/1 knapsack instance. Since the costs are integers, we can use a 1D DP array where dp[j] represents the maximum value achievable with a budget of exactly j tokens. The recurrence relation for each optional item is: dp[j] = max(dp[j], dp[j - cost] + value), iterating backwards through the budget to ensure each item is only used once.

2. Algorithm Approach

The solution follows a two-phase approach:

1. Preprocessing Pinned Items: Iterate through all snippets. Sum the costs and values of all pinned items. Subtract the total pinned cost from the given budget. If the result is negative, clamp it to 0.
2. 0/1 Knapsack on Optional Items: Filter out the pinned items to get a list of optional snippets. Apply the standard 1D DP knapsack algorithm on these optional items using the adjusted budget.
3. Combine Results: The final answer is the sum of the total pinned value and the maximum value obtained from the DP table for the optional items.

This approach leverages the additive nature of the problem: the pinned items are a constant offset, and the optional items form an independent optimization subproblem.

3. Step-by-Step Strategy

1. Initialize accumulators: Create variables pinned_cost = 0, pinned_value = 0, and an empty list optional_items.
2. Partition snippets: Loop through each snippet in snippets:

• If snippet["pinned"] is True, add its cost to pinned_cost and its value to pinned_value.
• Otherwise, append the snippet to optional_items.

3. Adjust budget: Compute remaining_budget = max(0, budget - pinned_cost).
4. Initialize DP array: Create a list dp of length remaining_budget + 1, initialized to 0. dp[j] will store the max value for budget j.
5. Process optional items: For each item in optional_items:

• Let c = item["cost"] and v = item["value"].
• Iterate j from remaining_budget down to c:
• Update dp[j] = max(dp[j], dp[j - c] + v).

6. Return result: Return pinned_value + dp[remaining_budget].

4. Common Pitfalls

• Forgetting to clamp the budget: If pinned_cost > budget, the remaining budget should be 0, not negative. Using a negative index in Python would wrap around and produce incorrect results.
• Forward iteration in DP: The inner loop for the knapsack must iterate backwards (from remaining_budget down to c). Forward iteration would allow the same item to be used multiple times, turning it into an unbounded knapsack problem.
• Including pinned items in DP: Pinned items should not be part of the DP loop. They are already accounted for in pinned_value and pinned_cost. Including them again would double-count their value.
• Off-by-one errors: The DP array size must be remaining_budget + 1 to include index remaining_budget. The loop bounds must be carefully checked to avoid index errors.
• Ignoring zero-cost items: If an optional item has cost 0, the backward loop from remaining_budget to 0 will still work correctly, but ensure the loop condition handles c = 0 properly (i.e., the loop runs from remaining_budget down to 0).

5. Time & Space Complexity

• Time Complexity: $O(n \cdot B)$, where $n$ is the number of optional snippets and $B$ is the remaining budget after subtracting pinned costs. The preprocessing step is $O(n)$, and the DP step dominates.
• Space Complexity: $O(B)$, due to the 1D DP array. This is an optimization over the 2D DP table, which would require $O(n \cdot B)$ space.

This complexity is efficient for typical token budgets (e.g., $B \leq 10^4$) and snippet counts (e.g., $n \leq 10^3$), making it suitable for real-time context packing in AI agents.