Greedy + Dp + Topo
unknown
java
21 days ago
3.9 kB
2
Indexable
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; } }
Editor is loading...
Leave a Comment