コイン支払い問題（１）の考察

　コイン支払い問題（１）の考察を示します。

（考察）問題（１）を解くBasicプログラム

Public A(100): ' コインの金額。
Public B(100): ' コインの最大個数。
Public X(100): ' 解。
Public COUNT:  ' 解の個数。
Public KIND:   ' コインの種類。
Public M:      ' 指定金額。
'
' 初期設定。
KIND=3
A(1)=100: A(2)=50: A(3)=10
B(1)=2: B(2)=4: B(3)=5
M=250
'
Call Gen(1,0)
End
'
Sub Gen(K,SUM)
  If K > KIND Then
    If SUM = M Then
      COUNT=COUNT+1
      Print Using"#####: ";COUNT;
      For J=1 To KIND
        Print Using"#####円 ##個";A(J);X(J);
      Next J
      Print
    End If
    Exit Sub
  End If  
  '
  For I=0 To B(K)
    X(K)=I
    If SUM+A(K)*X(K) > M Then Exit For
    Call Gen(K+1,SUM+A(K)*X(K))
  Next I
End Sub

実行結果

1: 100円 0個 50円 4個 10円 5個
2: 100円 1個 50円 2個 10円 5個
3: 100円 1個 50円 3個 10円 0個
4: 100円 2個 50円 0個 10円 5個
5: 100円 2個 50円 1個 10円 0個
OK