VENDING MACHINE PROBLEM (DYNAMIC PROGRAMMING SOLUTION)

VENDING MACHINE PROBLEM (DYNAMIC PROGRAMMING SOLUTION)

namespace VendingMachine
{
    class Currency
    {
        public int Denomination { get; set; }
        public int Count { get; set; }

        public Currency(int denom, int count)
        {
            this.Denomination = denom;
            this.Count = count;
        }
    }

    class Program
    {
        static void TenderChange(List<Currency> inventory, int changeToReturn)
        {
            int[,] DP = new int[inventory.Count, changeToReturn + 1];
            int[,] CountTable = new int[inventory.Count, changeToReturn + 1];

            int currencyIndex = 0;

            //Advance the index to denomination from which it is optimal to start.
            while (inventory[currencyIndex].Denomination > changeToReturn) currencyIndex++; 

            for (; currencyIndex < DP.GetLength(0); currencyIndex++)
            {
                for (int change = 1; change < DP.GetLength(1); change++)
                {
                    GetSolution(DP, inventory, change, currencyIndex, CountTable);
                }
            }

            int tempChangeToReturn = changeToReturn;

            Print(DP);
            Console.WriteLine();
            Print(CountTable);

            if (DP[inventory.Count - 1, changeToReturn] == changeToReturn)
            {
                for (int i = inventory.Count-1; i >= 0; i--)
                {
                    if (tempChangeToReturn > 0)
                    {
                        Console.WriteLine(inventory[i].Denomination + "--->" + CountTable[i, tempChangeToReturn]);
                        tempChangeToReturn -= CountTable[i, tempChangeToReturn] * inventory[i].Denomination;
                    }
                    else break;
                }
            }
            else
            {
                Console.WriteLine("No solution possible");
            }
        }

        static void Print(int[,] mat)
        {
            for(int i=0;i<mat.GetLength(0);i++)
            {
                for (int j = 0; j < mat.GetLength(1); j++)
                {
                    Console.Write(mat[i, j] + "  ");
                }
                Console.WriteLine();
            }
        }

        static void GetSolution(int[,] DP, List<Currency> inventory, int change, int currencyIndex, int[,] countTable)
        {
            int numberOfCoins = change / inventory[currencyIndex].Denomination;
            if (numberOfCoins > inventory[currencyIndex].Count) numberOfCoins = inventory[currencyIndex].Count;

            if (currencyIndex - 1 >= 0)
            { 
                int i = 0;
                int tempChange = change;
                //Increase the coin count and check if optimal solution is possible.
                while (i<=numberOfCoins)    
                {
                    if (DP[currencyIndex - 1, tempChange] + i * inventory[currencyIndex].Denomination == change)
                    {
                        countTable[currencyIndex, change] = i;
                        DP[currencyIndex, change] = DP[currencyIndex - 1, tempChange] + i * inventory[currencyIndex].Denomination;
                        break;
                    }
                    i++;
                    tempChange -= inventory[currencyIndex].Denomination;
                }
            }
            else
            {
                if (numberOfCoins * inventory[currencyIndex].Denomination == change)
                {
                    countTable[currencyIndex, change] = numberOfCoins;
                    DP[currencyIndex, change] = numberOfCoins * inventory[currencyIndex].Denomination; ;
                }
                else
                    DP[currencyIndex, change] = 0;
            }
        }

        static void Main(string[] args)
        {
            List<Currency> inventory = new List<Currency>();
            inventory.Add(new Currency(10, 13));
            inventory.Add(new Currency(5, 30));
            inventory.Add(new Currency(1, 4));
            //inventory.Add(new Currency(5, 4));

            TenderChange(inventory, 16);
        }
    }
}