最少硬币问题(无穷硬币)

 1 /*贪心可能导致无解;
 2  硬币系统是10，7，5，1元，那么12元用贪心法得到的硬币数为3，而最少硬币数是2。
 3  对于此题，可以举个例子：
 4     若有1，5，7，10这四种货币，则易知
 5     1=1
 6     2=1+1
 7     3=1+1+1
 8     ……
 9     6=5+1
10  那么推下去可知
11          表示12这个面值需要的货币数，等于表示11或7或5或2需要的货币数+1。
12          那么题中若要求表示12所需用的最小货币数，只需寻找表示11或7或5或2需要的货币数中的最小值。
13
14  */
15
16  //硬币数无穷
17  #include <iostream>
18  #include <cstring>
19  using namespace std;
20
21  int coinValue[] = { 25, 21, 10, 5, 1 }; //硬币系统
22  int money = 63;//钱数
23  int coinUsed[100];//每种数量的钱币所需最少硬币数
24
25  void solve()
26  {
27      int i,j,k;
28      int len = sizeof(coinValue)/sizeof(coinValue[0]);
29      memset(coinUsed,0,sizeof(coinUsed));
30
31      for(i=1; i<=money; i++)//递推
32      {
33          int minCoins = i/coinValue[len-1];
34          int temp = 0;
35          for(j=0; j<len; j++)
36          {
37              if(i>=coinValue[j])
38              {
39                  temp = coinUsed[i - coinValue[j]] + 1;
40                  /*
41                  在temp赋初值为0时,下面的if不能和外层if并列,改为1貌似对了
42                  money=1时前几次 内层for未执行，此时 minCoins变为0了，到内层最后temp变为1，不过此时 minCoins还是0，所以就错了
43                  */
44                  if(minCoins>temp)
45                      minCoins = temp;
46              }
47
48          }
49          coinUsed[i] = minCoins;
50      }
51  }
52
53  int main()
54  {
55      int i,j,k;
56      solve();
57      cout<<coinUsed[money]<<endl;
58      while(1);
59      return 0;
60  }