Skip to content

Instantly share code, notes, and snippets.

@runewake2
Created January 24, 2017 05:15
Show Gist options
  • Save runewake2/660c9b98946af8d39f6764ba5b1cf581 to your computer and use it in GitHub Desktop.
Save runewake2/660c9b98946af8d39f6764ba5b1cf581 to your computer and use it in GitHub Desktop.
Solution to dynamic programming problem of creating optimal change with least number of coins. Solution includes greedy and dynamic problems as well as comparisons between them.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;
// The change problem :D
namespace DynamicProgramming
{
class Program
{
public readonly static Dictionary<String, int> coins = new Dictionary<String, int>()
{
{ "One", 1 },
{ "Three", 3 },
{ "Four", 4 },
};
static void Main(string[] args)
{
optimalChange[0] = new Dictionary<string, int>() {
{ "One", 0},
{ "Three", 0},
{ "Four", 0 },
};
for (int i = 1; i < 100; i++)
{
var changeDefault = CalculateChange(i);
var changeDynamic = CalculateChangeDynamic(i);
Console.WriteLine("DEFAULT " + i + ": " + Stringify(changeDefault) + " | " + CalculateCoinAmount(changeDefault));
Console.WriteLine("DYNAMIC " + i + ": " + Stringify(changeDynamic) + " | " + CalculateCoinAmount(changeDynamic));
Console.WriteLine();
}
Console.ReadLine();
}
private static Dictionary<string, int>[] optimalChange = new Dictionary<string, int>[100];
private static Dictionary<String,int> CalculateChangeDynamic(int change)
{
var resultingChangeAmounts = new Dictionary<string, int>();
int currentBestExchange = Int32.MaxValue;
foreach (var coin in coins)
{
int targetIndex = change - coin.Value;
if (targetIndex < 0)
{
continue;
}
int coinAmount = CalculateCoinAmount(optimalChange[targetIndex]);
if (coinAmount > currentBestExchange)
{
continue;
}
currentBestExchange = coinAmount;
var tempChange = new Dictionary<string, int>(optimalChange[targetIndex]);
int value = tempChange[coin.Key] + 1;
tempChange.Remove(coin.Key);
tempChange.Add(coin.Key, value);
resultingChangeAmounts = tempChange;
}
optimalChange[change] = resultingChangeAmounts;
return resultingChangeAmounts;
}
private static int CalculateCoinAmount(Dictionary<string, int> resultingChangeAmounts)
{
int coinCount = 0;
foreach (var coin in resultingChangeAmounts)
{
coinCount += coin.Value;
}
return coinCount;
}
private static Dictionary<String, int> CalculateChange(int change)
{
var resultingChangeAmounts = new Dictionary<string, int>();
foreach (var coin in coins.OrderByDescending((kv) => kv.Value))
{
int coinAmount = 0;
while (change >= coin.Value)
{
coinAmount++;
change -= coin.Value;
}
resultingChangeAmounts.Add(coin.Key, coinAmount);
}
return resultingChangeAmounts;
}
private static string Stringify(Dictionary<string, int> resultingChangeAmounts)
{
StringBuilder builder = new StringBuilder();
foreach (var coinAmount in resultingChangeAmounts)
{
builder.Append(coinAmount.Key);
builder.Append(":");
builder.Append(coinAmount.Value);
builder.Append(" ");
}
return builder.ToString();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment