Interview Question Categories

VENDING MACHINE PROBLEM (BACKTRACKING METHOD)

VENDING MACHINE PROBLEM (BACKTRACKING METHOD)


namespace VendingMachineProb
{
    struct Inventory
    {
        public int Denomination;
        public int Count;

        public Inventory(int d, int c)
        {
            Denomination = d;
            Count = c;
        }
    }

    class Program
    {
        public static void ReturnChange(ref int RetAmt, Inventory[] stock, int index, Inventory[] Result)
        {
            if (RetAmt <= 0) return;
            if (index >= stock.Length) return;
            int NoOfCoins = 0;
            int IntermediateVal = 0;

            NoOfCoins = RetAmt / stock[index].Denomination;
            if (NoOfCoins > stock[index].Count) NoOfCoins = stock[index].Count;
            //stock[index].Count -= NoOfCoins;
            Result[index].Count = NoOfCoins;
            Result[index].Denomination = stock[index].Denomination;
            IntermediateVal = NoOfCoins*stock[index].Denomination;
            RetAmt -= IntermediateVal;
            if (RetAmt == 0)
            {
                for(int i=0;i<Result.Length;i++)
                {
                    stock[i].Count -= Result[i].Count;
                    Console.WriteLine(Result[i].Denomination + "  " + Result[i].Count);
                }
                return;
            }
            if (index + 1 < stock.Length)
                ReturnChange(ref RetAmt, stock, index + 1, Result);
            else
            {
                RetAmt += IntermediateVal;
                Result[index].Count -= NoOfCoins;
                return;
            }

            while (RetAmt != 0)
            {
                if (Result[index].Count == 0)
                {
                    RetAmt += IntermediateVal;
                    return;
                }
                RetAmt += stock[index].Denomination;
                Result[index].Count--;

                if (index + 1 < stock.Length)
                    ReturnChange(ref RetAmt, stock, index + 1, Result);
                else return;
            }
        }

        static void Main(string[] args)
        {
            Inventory[] Stock = {
                                    new Inventory(50,1),
                                    new Inventory(25,3),
                                    new Inventory(10,3),
                                    new Inventory(1,3)
                                };
            int RetAmt = 80;
            //List<Inventory> l = new List<Inventory>();
            ReturnChange(ref RetAmt,Stock,0,new Inventory[4]);

            RetAmt = 78;
            ReturnChange(ref RetAmt, Stock, 0, new Inventory[4]);
        }
    }
}

No comments:

Post a Comment