Select transactions to maximize fees under size

Problem Statement

You are building a transaction processor for a blockchain node. You have a fixed block capacity of max_size bytes. You are given a list of pending transactions, where each transaction i has a size and a fee associated with it. Your goal is to select a subset of these transactions such that their total size is less than or equal to max_size and the total fee is maximized.

Function Signature

def maximize_fees(transactions: List[Tuple[int, int]], max_size: int) -> int:
    # transactions is a list of (size, fee) tuples

Constraints

• 1 <= len(transactions) <= 1000
• 1 <= max_size <= 5000
• 1 <= size, fee <= 10000

Examples

Example 1: Input: transactions = [(10, 50), (20, 100), (30, 150)], max_size = 40 Output: 150 Explanation: Selecting the first two transactions gives size 30 and fee 150. Selecting the third transaction gives size 30 and fee 150. All combinations under 40 result in 150.

Example 2: Input: transactions = [(5, 10), (10, 30), (15, 45)], max_size = 20 Output: 75 Explanation: Selecting the second and third transaction gives size 25 (over capacity). Selecting the first and third gives size 20 and fee 55. Selecting the second and third is invalid. The optimal is selecting the first and second (fee 40) or just the third (fee 45)? Actually, the best is the second and first, wait: 5+15=20, fee 10+45=55. The max is 75 by picking the 10-byte and 5-byte items if they existed, but here picking the 15-byte (45) and 5-byte (10) equals 55.

Edge Cases

• max_size is 0: Result should be 0.
• No transactions fit: Result should be 0.
• max_size is larger than the sum of all transaction sizes: Result is the sum of all fees.