summerofbitcoin_challenge

Summer of Bitcoin challenge task 1.

Applied Knapsack algorithm for implementation of Greedy based technique where we are doing the following:-

(1) Sorting the transactions in the order of fee/weight. (2) Using a set (implementing a heap structure) we check if all the parents are already present in the block or not. (3) If step 2 is true, we include the transaction and update fee and weight and erase it from current set otherwise, go to next higher transaction.

Time complexity: O(n²)

The main code is written in C++in solution.cpp file and the output block generated in block.txt

Output:

Total number of transactions read: 5214
Number of tx in final block 3174
Total fee in curr block : 5696031
Total weight : 3.99994e+06
Percentage of weight: 99.9984 %

Screenshot of output:

References:

Geeks For Geeks Fractional Knapsack Problem

mempool

Binace

Heap