貪欲なアルゴリズム

会社で誰かが貪欲なアルゴリズムの問題を出していたので，日本の硬貨単位に合わせたものを解いてみた．DPを使わなければまぁ大概はこのような解になるだろう．

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

int coins[] = { 1, 5, 10, 50, 100, 500 };
int nums[] = { 6, 3, 4, 5, 3, 2 };

void useCoins(int amounts, std::vector<std::pair<int,int>*>& pV) {
 int num;
 for (int i = sizeof(coins) / sizeof(int) - 1; i >= 0; i--) {
  if (amounts <= 0) {
   return;
  }
  num = std::min(amounts / coins[i], nums[i]);
  amounts -= num * coins[i]; 
  pV.push_back(new std::pair<int,int>(coins[i], num));  
 }
}

int main() {
 std::vector<std::pair<int,int>*> v;
 useCoins(1280, v);
 for_each(v.begin(), v.end(), [](std::pair<int,int>* x){ std::cout << x->first << ":" << x->second << std::endl; });

}