Context Window Packing
A retrieval-augmented pipeline has a fixed token budget for the model's context window and a set of candidate passages, each with a token cost and a relevance score. Pick a subset that maximises total relevance without exceeding the budget. (This is a 0/1 knapsack — the LLM scene is just the framing; the algorithm is classical DP.)
Problem
Given n items each with cost[i] (tokens) and value[i] (relevance), and a budget B, choose a subset maximising total value subject to total cost ≤ B. Each item is taken at most once. Return the maximum achievable value.
Input
Integer n (1 ≤ n ≤ 2000), budget B (0 ≤ B ≤ 10^4), arrays cost and value of length n (0 ≤ cost[i] ≤ B; 0 ≤ value[i] ≤ 10^6).
Output
A single integer — the maximum total value within budget.
Constraints
- 1 ≤ n ≤ 2000
- 0 ≤ B ≤ 10,000
- Each item used at most once (0/1 knapsack)
Examples
Example 1
Input
cost = [3, 4, 5], value = [30, 50, 60], B = 8
Output
90
Items 0 and 2 cost 3+5=8 ≤ 8 with value 30+60=90. Items 1 and 0 cost 7 with value 80; items 1 and 2 cost 9 > 8.
Example 2
Input
cost = [2, 2, 2], value = [5, 5, 5], B = 3
Output
5
Budget 3 fits only one item (any two cost 4 > 3), so the best is a single value of 5.