Block Packing With Dependencies
HardDynamic Programming ยท Coinbase
Given pending transactions txs, where txs[i] = [fee, size, parent], choose the transactions to put in a block and return the largest total fee you can collect.
parent is the index of another transaction in txs, or -1 if there is none. A transaction can be in the block only if its parent is also in the block. The sizes of the chosen transactions must add up to at most capacity. An empty block is allowed.
Example 1
- Input:
- txs = [[2, 3, -1], [9, 4, 0], [5, 2, -1], [4, 3, 2]], capacity = 7
- Output:
- 11
- Explanation
- Transactions 0 and 1 have size 7 and fee 11. Transaction 1 alone would be worth more per unit of size, but it cannot be included without 0.
Example 2
- Input:
- txs = [[6, 4, -1], [5, 3, -1], [5, 3, -1]], capacity = 6
- Output:
- 10
Example 3
- Input:
- txs = [[1, 1, -1], [1, 1, 0], [10, 1, 1]], capacity = 2
- Output:
- 2
- Explanation
- The fee-10 transaction needs both ancestors, which would take size 3.
Constraints
0 <= txs.length <= 2000 <= fee <= 10^6and1 <= size <= 1000for every transactionparentis-1or a valid index other thani, and followingparentlinks never leads back toi0 <= capacity <= 1000