找零使用最少硬幣(CPP版參考解)

輸入第一列 t 代表有 t 組資料，每組2列：第1列  n 種 ,  m元，第2列 n 種的面額

範例輸入：
3
5 50
1 3 5 7 13
5 50
1 5 6 7 15
8 125
1 2 3 10 11 12 20 21
範例輸出
6
4
6
參考程式碼：
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 20;
const int MaxM = 50000;
const int INF = MaxM+1;
int a[MaxN];
int d[MaxM+1];
int n,m;

int dp(int r)
{
   int i,v , u = INF, j=n;
   if(d[r]<INF) return d[r];  // 已有值
   for(i=n-1; i>=0; --i)
   {
if(r>a[i])
{
   v = 1 + dp(r-a[i]); // 金額 r = a[i] + 剩下的金額
   if(v < u)   u=v;
}
   }
   d[r] = u;
   return u;
}

int main(void)
{
   int i,j,k,t;
   cin >> t; // t組資料
   while( t-- )
   {
      cin >> n >> m;  //每組兩列，第1列 n種硬幣， 要換 m 元
      for(i=0; i<n; ++i) cin >> a[i];
      sort(a,a+n) ; //有需要可能需排序
// 設定初值，1個
      for(i=0; i<=m; ++i) d[i] = INF;  // fill
      for(i=0;i<n;++i)  d[a[i]] = 1; // 硬幣面值的數額只需換1個
      int ans =  dp(m);
      cout << ans << endl;
   }
   return 0;

}