Priority Context Packing Under a Token Budget

Problem Statement

Assemble the highest-value context that fits a token budget. Each candidate snippet has a token cost and a value; some are pinned (must always be included). Maximize total value without exceeding the budget.

Background

This is 0/1 knapsack with mandatory items. Pinned snippets are always included and their cost is subtracted from the budget first (if pinned items alone exceed the budget, they are still all included and the remaining budget is treated as 0 for the rest). The remaining optional snippets are chosen to maximize value within the leftover budget via exact 0/1 knapsack (integer costs). Return the max total value (pinned + chosen optional).

Your Task

def pack_context(snippets, budget):

snippets: list of {"cost": int, "value": int, "pinned": bool}.
Return the maximum achievable total value (int).

Input Format

snippets (list of dicts), budget (int).

Output Format

A single int (max total value).

Sample

s = [{"cost":5,"value":10,"pinned":True},{"cost":4,"value":40,"pinned":False},{"cost":3,"value":50,"pinned":False}]
print(pack_context(s, 10))

Output:

Example:

Input:

s = [{"cost":5,"value":10,"pinned":True},{"cost":4,"value":40,"pinned":False},{"cost":3,"value":50,"pinned":False}]
print(pack_context(s, 10))

Output:

Reasoning:

Pin costs 5 (value 10), leaving 5. Both optional (4+3=7) don't fit; best single is value 50 (cost 3). 10+50=... but 4 fits too? 4 alone=40. Best within 5 is the cost-3 value-50 => 10+50=60? See note.

Constraints:

0 <= budget <= 5000, costs/values are non-negative ints, len(snippets) <= 200.
All pinned items are always counted; remaining budget = max(budget - sum(pinned costs), 0).
Optional items chosen by exact 0/1 knapsack on the remaining budget.