POJ.3040 Allowance

1.Problem
http://poj.org/problem?id=3040

2.Idea
Need to do 2 run greedy calculation. Build a valid coin combination for a allowance as much as close to value c with the following approach:
first run: Start filling from biggest valued coin, and taking as many as possible
second run: If there is still remainder, this time start use smallest valued coins.

3.Source:

 struct Bill {  
      int v, b;  
      bool operator < (const Bill &a)const {  
           return v > a.v;  
      }  
 } Bills[22];  
 int use[22];  
 int n, c;  
 int k = 0;  
 int ans = 0;  
 int main()  
 {  
      cin >> n >> c;  
      for (int i = 0; i < n; i++) {  
           int v, b;  
           cin >> v >> b;  
           Bills[i].v = v;  
           Bills[i].b = b;  
      }  
      // sort by decreasing order of coin value  
      sort(Bills, Bills + n);  
      while (1) {  
           int rest = c;  
           memset(use, 0, sizeof use);  
           // use coins from biggest size:like 50, 10, 5, 1  
           for (int i = 0; i < n; i++) {  
                int tmp = min(Bills[i].b, rest / Bills[i].v);  
                use[i] = tmp;  
                rest -= tmp * Bills[i].v;  
           }  
           // if still need, this time use coin from smallest value: like 1, 5, 10, 50  
           int i = n - 1;  
           while (rest > 0 && i >= 0) {  
                int tmp = min((Bills[i].b - use[i]), (int)ceil((double)rest / (double)Bills[i].v));  
                use[i] += tmp;  
                rest -= tmp * Bills[i].v;  
                i--;  
           }  
           // if can't fill a full allowance, to leave  
           if (rest > 0) break;  
           // get the max possible allowance number for the current combination  
           int MinUse = INF;  
           for (int i = 0; i < n; i++) {  
                if (use[i]) {  
                     MinUse = min(MinUse, Bills[i].b / use[i]);  
                }  
           }  
           // if can't get any number then leave  
           if (MinUse == INF) break;  
           // subtruct used coins from respective vars  
           for (int i = 0; i < n; i++) {  
                Bills[i].b -= (use[i] * MinUse);  
           }  
           ans += MinUse;            
      }  
      cout << ans << endl;  
      return 0;  
 }