DSAhardArrays~35m

The Context Budget

Problem

You are an engineer on Anthropic's inference team. When a conversation exceeds the context window, you must decide which messages to retain. Each message has a token cost and an importance score. You want to maximize the total importance of retained messages without exceeding the token budget.

Given arrays token_costs and importance_scores for n messages, and a token_budget, return the maximum total importance score achievable without exceeding the budget. Each message can be included at most once.

Examples

Example 1

Input: ([5, 4, 3], [10, 9, 8], 7)

Output: 17

Greedy picks the highest importance (10, cost 5) leaving only 2 tokens — score 10. DP finds messages 2+3 (scores 9+8=17, cost 4+3=7). Optimal is 17.

Example 2

Input: ([8, 4, 4], [100, 60, 60], 8)

Output: 120

Greedy takes the highest importance message (100, cost 8) — score 100. DP skips it and takes both cheaper messages (60+60=120, cost 4+4=8). Optimal is 120.

Example 3

Input: ([2], [10], 4)

Output: 10

Only one message of cost 2. Despite budget being 4, each message can only be included once — answer is 10 not 20.

Constraints

›1 <= n <= 100
›1 <= token_costs[i] <= 1000
›1 <= importance_scores[i] <= 1000
›1 <= token_budget <= 10000

Loading question…