Usage

Open the repository in the terminal and type the following commands :

$ make
$./exe

Ensure that the input is in mempool.csv file. Output will be written to block.txt

Approach

Step 1 : Reduction
In this step we select or reject some items in the following manner :

1. Reject items whose weight is greater than W_max
2. Reject items whose sum of weight of ancestors is greater than W_max

Step 2: Selection of Method
We look at the number of items after Step 1 . We essentially have 2 methods :

1. Dynamic Programming - We essentially choose the (subgraph,remaining weight) as our state and iterate through all possibilities based on our choices. This might take O(2ⁿ) in the worst case (both time and memory wise). So we only go for this method if the number of items after reduction is less than 25 .This problem is called precedence constrained knapsack problem in literature and the algorithm I have used have been adapted from this academic paper

2. Greedy Method - In this method we select the item in a specific order which we believe will give us better results. In this problem I have used 4 different heuristics and have finally selected the best answer out of them

The Greedy Heuristics

1. Topological order - We process the items in their topological order. Intuitively this makes sense because in this case we decide whether to choose the ancestors before choosing for the children which is suitable in this porblem (because the choice of an ancestor affects the children not vice versa).
2. Topological with fee/weight bias - The topological order is not unique. A subset of such orders can be generated by the Kahn's algorithm . Here I have considered such topological orders where the items with higher fee/weight appear earlier (without violating the topological order , of course). This has been done by modifying the Kahn's algorithm.
3. fee/weight order - Here all the items are considered in decreasing order of fee/weight ensuring the condition that an item is taken only if all its ancestors are taken.
4. Tree wise with fee/weight bias ( does not work in the general case ) - In general case, if we consider the items as nodes in a graph , we get a Directed Acyclic Graph. However , I noticed that for the given input specifically , the graph is also a collection of Directed Trees. This allows us to process the items taking one tree at a time. The trees with highest fee/weight ratio of the root is selected first.

Results

weight of transactions selected = 3999936
total fee of transactions selected =5696031
Look in block.txt to see the list of transactions in topological order.