Tool Call Sequence Budget
An LLM agent has k callable tools. To answer a question it must choose an ordered sequence of tool calls (no tool repeats). Each tool has a fixed token cost and a fixed information gain. The agent must produce the highest-gain sequence whose total token cost stays under a budget. The agent emits sequences (not sets) because tool order changes downstream behaviour.
Problem
Given two arrays cost and gain of length k (where cost[i] is the token cost and gain[i] is the information gain of tool i), and an integer budget, return the maximum total gain achievable by any ordered sequence of distinct tool indices whose total cost is ≤ budget. The sequence may use any subset of tools in any order, but no tool more than once.
Input
Integers k (1 ≤ k ≤ 12) and budget (1 ≤ budget ≤ 10^6). Arrays cost and gain of length k with 1 ≤ cost[i] ≤ budget and 1 ≤ gain[i] ≤ 10^6.
Output
A single integer — the maximum total gain.
Constraints
- 1 ≤ k ≤ 12 (small to allow exponential enumeration)
- 1 ≤ budget ≤ 10^6
- Each tool index used at most once
- Order of the sequence does not affect cost or gain in this formulation — but the agent records the order, so the answer is across all permutations
- Empty sequence is allowed (gain = 0)
Examples
Example 1
Input
k = 3, cost = [3, 4, 5], gain = [10, 12, 15], budget = 7
Output
22
Pick tools 0 and 1: cost 3+4=7 ≤ 7, gain 10+12=22. Pick 0 and 2: 3+5=8 > 7. Pick 1 and 2: 4+5=9 > 7. Best is {0,1} → 22.
Example 2
Input
k = 1, cost = [5], gain = [10], budget = 4
Output
0
Tool 0 cost 5 > 4, can't use. Empty sequence → 0.