贪心算法 - 钱币找零问题

深藏阁楼爱情的钟 2022-02-21 07:10 254阅读 0赞

这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？

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

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

用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。

class Program
        {
    
            static void Main(string[] args)
            {
                int[] count = { 3, 0, 2, 1, 0, 3, 5 };
                int[] value = { 1, 2, 5, 10, 20, 50, 100 };
                int k = 47;
                int money = 100;
                int remain = money - 47;
                List<int> moneyList = GetMoney(new List<int>(), remain, count, value);
                //List<int> moneyList = GetMoney_Iteration(remain, count, value);
    
                foreach (var item in moneyList)
                {
                    Console.Write(item + " ");
                }
    
                Console.ReadKey();
            }
            // 递归法
            private static List<int> GetMoney(List<int> resultList,int remain,int[] count,int[] value)
            {
                if (remain <= 0) return resultList;
    
                for (int i = count.Length - 1; i >= 0; i--)
                {
                    if (remain >= value[i] && count[i] > 0)
                    {
                        resultList.Add(value[i]);
                        remain -= value[i];
                        count[i] -= 1;
                        break;
                    }
                }
    
                return GetMoney(resultList,remain ,count,value);
            }
    
            // 迭代法
            private static List<int> GetMoney_Iteration(int remain,int[] count,int[] value)
            {
                List<int> resultList = new List<int>();
                for (int i = count.Length - 1; i >= 0; i--)
                {
                    if (remain >= value[i] && count[i] > 0)
                    {
                        int h = remain / value[i];
                        // Console.WriteLine(h);
                        for (int j = 0; j < h; j++)
                        {
                            if (count[i] > 0)
                            { 
                                resultList.Add(value[i]);
                                count[i] -= 1;
                                remain -= value[i];
                            }
                        }
                    }
                }
                return resultList;
            }
        }