Greedy + Dp + Topo

public class DPBasedCalc implements FeesCalculator {

    private double calculateFees(ArrayList<Transaction> txns, int blockSize, int n){
        if(n==0){
            if(blockSize >= txns.getFirst().getSize()){
                return txns.getFirst().getFee();
            }
            return 0;
        }

        if(blockSize == 0){
            return 0;
        }

        double maxVal = calculateFees(txns, blockSize, n-1);

        if(blockSize> txns.get(n).getSize()){
            maxVal = Math.max(maxVal, txns.get(n).getFee() + calculateFees(txns, blockSize - txns.get(n).getSize(), n-1));
        }

        return maxVal;
    }

    @Override
    public double calculateMaxFees(ArrayList<Transaction> txns, int blockSize) {
        return calculateFees(txns, blockSize, txns.size()-1);
    }
}


public class GreedyCalc implements FeesCalculator {

    @Override
    public double calculateMaxFees(ArrayList<Transaction> txns, int blockSize) {
        PriorityQueue<Ratio> pq = new PriorityQueue<>(Comparator.comparingDouble(Ratio::getRatio).reversed());

        for(int i = 0;i<txns.size();i++){
            pq.add(new Ratio((double) txns.get(i).getFee()/ (double) txns.get(i).getSize(), i));
        }
        double ans = 0.0;
        while(blockSize > 0){
            Ratio largestRatio = pq.poll();
            int txnIdx = largestRatio.getId();

            Transaction txn = txns.get(txnIdx);

            int capacity = Math.min(blockSize, txn.getSize());
            ans += (largestRatio.getRatio() * capacity);
            blockSize -= capacity;
        }
        return ans;
    }
}

public class TopoCalc implements FeesCalculator {
    private void sortTxnIds(ArrayList<ArrayList<Integer>> adj, Stack<Integer> st, HashSet<Integer> visited, Integer n){
        visited.add(n);

        for(int i = 0;i<adj.get(n).size();i++){
            if(!visited.contains(adj.get(n).get(i)))
                sortTxnIds(adj, st, visited, adj.get(n).get(i));
        }

        st.add(n);
    }

    @Override
    public double calculateMaxFees(ArrayList<Transaction> txns, int blockSize) {
        HashMap<Integer, Transaction> txnIdMap = new HashMap<>();
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        adj.add(new ArrayList<>(List.of(1)));
        adj.add(new ArrayList<>(List.of(2)));
        adj.add(new ArrayList<>(List.of(3)));
        adj.add(new ArrayList<>());
        HashSet<Integer> visited = new HashSet<>();
        Stack<Integer> sortedIds = new Stack<>();

        for (Transaction txn : txns) {
            txnIdMap.put(txn.getId(), txn);
            if (!visited.contains(txn.getId())) {
                sortTxnIds(adj, sortedIds, visited, txn.getId());
            }
        }
        ArrayList<Transaction> newTxnList = new ArrayList<>();
        while (!sortedIds.empty()){
            newTxnList.add(txnIdMap.get(sortedIds.pop()));
        }

        double ans = 0;
        for(Transaction txn: newTxnList){
            if(txn.getSize() > blockSize){
                break;
            }
            ans += txn.getFee();
            blockSize -= txn.getSize();
        }
        return ans;
    }
}

public interface FeesCalculator {
    double calculateMaxFees(ArrayList<Transaction> txns, int blockSize);
}


public class Transaction {
    private int id;
    private int fee;
    private int size;

    public Transaction(int id, int fee, int size) {
        this.id = id;
        this.fee = fee;
        this.size = size;
    }

    public int getId() {
        return id;
    }

    public int getFee() {
        return fee;
    }

    public int getSize() {
        return size;
    }
}

public class Ratio {
    private double ratio;
    private int id;

    public Ratio(double ratio, int id) {
        this.ratio = ratio;
        this.id = id;
    }

    public double getRatio() {
        return ratio;
    }

    public int getId() {
        return id;
    }
}