C# 贪心算法 -- 钱币找零问题

2021-02-20 10:07发布

问题描述:

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元,至少要用多少张纸币?用贪心算法的思想,很显然,每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。

代码实现:

using System;


namespace _5_2_1贪心算法_钱币找零问题

{

    class Program

    {

        static void Main(string[] args)

        {

            //纸币面值和用于该面值所对的张数

            int[] Value = { 1, 2, 5, 10, 20, 50, 100 };

            int[] Count = { 3, 0, 2, 1, 0, 3, 5 };


            int[] result = Change(335, Count, Value);


            foreach (int item in result)

            {

                Console.Write(item +" ");

            }


            Console.ReadKey();

        }


        //参数:要换的钱,拥有的钱面值以及对应张数。

        public static int[] Change(int k,int[] count,int[] value)

        {

            if (k == 0) { return new int[value.Length+1]; }

            int index = value.Length - 1;

            int[] result = new int[value.Length + 1];

            while (true)

            {

                if (k <= 0 || index <= -1) break;

                if (k > count[index] * value[index])

                {

                    result[index] = count[index];

                    k -= count[index] * value[index];

                }

                else

                {

                    result[index] = k / value[index];

                    k -= result[index] * value[index];

                }

                index--;

            }

            result[value.Length] = k;

            return result;

        } 

    }

}




作者:Czhenya

链接:https://czhenya.blog.csdn.net/article/details/78997364

来源:CSDN
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。