找零使用最少硬幣(VB版)

輸入第一列 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
參考程式碼：
 Const Maxn As Integer = 20 ' 硬幣種類最多 20種
 Const Maxm As Integer = 500000 ' 要換的金額最多 50萬
 Dim n, m As Integer
 Dim a(Maxn) As Integer '硬幣種類及面額
 Dim d(Maxm) As Integer '每一種面額 可換的 最少 零錢數 ，, 未設定為 Maxm+1
 Const inf As Integer = Maxm + 1
 Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
   FileOpen(1, "in1.txt", OpenMode.Input)
   'FileOpen(2, "in2.txt", OpenMode.Input)
   FileOpen(3, "out.txt", OpenMode.Output)
   For fn = 1 To 1  '只一個檔
      If fn = 2 Then PrintLine(3) '若第2檔，空一列
      Dim t As Short = LineInput(fn)
      For i = 1 To t
          Dim nm() = LineInput(fn).Split(" ")  '讀第一列： n  m
          n = nm(0) : m = nm(1)
          For j = 0 To m
              d(j) = inf
          Next
          Dim dat() = LineInput(fn).Split(" ") '讀第二列： n 個硬幣的 面額
          For j = 0 To n - 1
              a(j) = dat(j)
              d(a(j)) = 1
          Next
          Array.Sort(a, 0, n) '排序
          Dim ans = dp(m) '呼叫 dp( )傳回 m 元所需最少硬幣數
          PrintLine(3, ans & "")
      Next i
  Next fn
  End
End Sub
 Function dp(ByVal r As Integer) As Integer  '金額 r 最少需換 dp(r)=u 個硬幣
    Dim u As Integer = inf, v As Integer
    If d(r) < inf Then Return d(r) '已呼叫過不需重複
    For i = n - 1 To 0 Step -1
        If r > a(i) Then
            v = 1 + dp(r - a(i))
            If v < u Then u = v
        End If
    Next
    d(r) = u
    Return u
End Function