A miner builds the next block from the mempool (the waiting transactions) and keeps every fee it includes. Each transaction is a tuple (txid, size, fee, parent):
txidis a unique string,size >= 1andfee >= 0are integers,parentisNoneor thetxidof another transaction that appears earlier in the list. A transaction spends an output of its parent, so it may go into the block only if its parent does too (and so, recursively, all its ancestors). A parent can have many children.
Implement
max_block_fee(mempool: list[tuple[str, int, int, str | None]], block_size: int) -> int
returning the largest total fee of a set of transactions that respects every parent rule and whose total size is at most block_size.
mempool = [
("a", 4, 2, None),
("b", 3, 9, "a"), # rich child of a cheap parent
("c", 5, 6, None),
("d", 2, 3, None),
]
max_block_fee(mempool, 7) # 11 (a + b: size 7, fee 11)
max_block_fee(mempool, 6) # 6 (c alone; b needs a, and a + d earns only 5)
max_block_fee(mempool, 14) # 20 (everything)
max_block_fee(mempool, 1) # 0
Constraints: up to 300 transactions, block_size <= 3000, sizes and fees up to 10**6.
Greedy by fee per byte fails twice over: it can use the block's capacity badly, and it ignores that a child's fee is only reachable through its parent. Trying every subset is exponential; aim for O(n · block_size).
Show hint
the parent links form a forest. List the transactions in pre-order (each parent right before its subtree): then every subtree is a contiguous stretch of that list, and leaving a transaction out means jumping past its whole stretch.