noj 1063 Coins（DFS）

题意：有10种面值为 1, 2, 5, 10, 20, 50, 100, 200, 500 ， 1000 的钱  每种钱有一定的数量 给你一个总钱数，要求找出最少的钱币数量 如果找不出输出-1

思路：原以为可以用贪心解，但先付大钱，可能会无解（但其实是有解的） 用动态规划解 但你不知总钱数的范围 无法建数组 最后改用DFS深搜实现

//125MS      204K
#include <stdio.h>
int coin[] = {1,2,5,10,20,50,100,200,500,1000};
int num[11];
int ans[11],flag;

void dfs (int pay,int p)
{
      if (flag)    //当前以找到 返回
              return ;
      if (p == -1) //如果已经找完所有面值的钱&& 钱数为0 说明找到 flag == 1
      {
              if (pay == 0)
                      flag = 1;
              return ;
      }
      int i,max = pay/coin[p];
      if (max > num[p])        //用该面值的钱最多能付多少 从多到少一张张的找
              max = num[p];
      for (i = max;i >= 0;i --)
      {
              ans[p] = i;
              dfs(pay-i*coin[p],p-1);
              if (flag)
                      return ;
      }
}

int main ()
{
      int i,count;
      while (1)
      {
              count = 0;
              flag = 0;
              for (i = 0; i < 11; i ++)
              {
                      ans[i] = 0;
                      scanf ("%d",&num[i]);
                      if (num[i] == 0)
                      count ++;
              }
              if (count == 11)
              break;
              dfs (num[10],9);
              if (flag)
              {
                      int res = 0;
                      for (i = 0;i < 10;i ++)
                              res += ans[i];
                      printf ("%dn",res);
              }
              else
                      printf ("-1n");
      }
      return 0;
}