Created
December 22, 2018 14:14
-
-
Save Habush/5d459dc31de5b44d739c8aea02e430b3 to your computer and use it in GitHub Desktop.
The maximum possible reward is 14.2593 BTC
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Program | |
{ | |
/// <summary> | |
/// This problem is an optimization problem specifically 0-1 Knapsack problem which can be solved using dynamic programming approach | |
/// </summary> | |
/// <param name="args"></param> | |
static void Main(string[] args) | |
{ | |
IList<Tuple<int, int, double>> transactions = new List<Tuple<int, int, double>>(); | |
var lines = File.ReadAllLines("data/input.txt"); | |
for (int i = 1; i < lines.Length; i++) | |
{ | |
var tx = lines[i].Split('\t'); | |
var id = int.Parse(tx[0]); | |
var weight = int.Parse(tx[1]); | |
var fee = double.Parse(tx[2]); | |
transactions.Add(Tuple.Create(id, weight, fee)); | |
} | |
int max = 1000000; | |
var totalFee = FindMaxFee(transactions, max) + 12.5; | |
Console.WriteLine($"Maximum reward is: {totalFee} BTC"); | |
} | |
/// <summary> | |
/// This method takes a input data as a list of tuples and the maximum number of bytes and returns the maximum possible fee | |
/// </summary> | |
/// <param name="input"> | |
/// The input is a list that contains (id, num of bytes, fee) tuples obtained from the input.txt file | |
/// </param> | |
/// <param name="maxBytes"> | |
/// The number of maximum bytes. In this particular solution it is 1000000 | |
/// </param> | |
/// <returns></returns> | |
static double FindMaxFee(IList<Tuple<int, int, double>> input, int maxBytes) | |
{ | |
double[,] table = new double[input.Count + 1, maxBytes + 1]; | |
for (int i = 1; i < input.Count + 1; i++) | |
{ | |
int weight = input[i - 1].Item2; | |
double value = input[i - 1].Item3; | |
for (int j = 1; j < maxBytes + 1; j++) | |
{ | |
if (weight > j) | |
{ | |
table[i, j] = table[i - 1, j]; | |
} | |
else | |
{ | |
table[i, j] = Math.Max( | |
value + table[i - 1, j - weight], | |
table[i - 1, j] | |
); | |
} | |
} | |
} | |
double result = 0; | |
int limit = maxBytes; | |
for (int i = input.Count; i > 0; i--) | |
{ | |
bool solution = Math.Abs(table[i, limit] - table[i - 1, limit]) > 0; | |
if (solution) | |
{ | |
result += input[i - 1].Item3; | |
int weight = input[i - 1].Item2; | |
limit -= weight; | |
} | |
} | |
return Math.Round(result, 4); //round to the last 4 digits | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment