Skip to content

Instantly share code, notes, and snippets.

@Habush
Created December 22, 2018 14:14
Show Gist options
  • Save Habush/5d459dc31de5b44d739c8aea02e430b3 to your computer and use it in GitHub Desktop.
Save Habush/5d459dc31de5b44d739c8aea02e430b3 to your computer and use it in GitHub Desktop.
The maximum possible reward is 14.2593 BTC
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