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

问题描述：

假设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; } }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
 

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/78997364