動的計画法 c言語

【問題】

額面がB1, B2,..., Bm 円のm種類の紙幣を使って総額n円を支払うときの紙幣の最小枚数を求なさい。各額面の紙幣は何度でも使用できる。

入力
最初の行に整数nと整数m、次の行に空白区切りでm種類の紙幣の額面
n m
B1 B2 ... Bm

出力
必要な紙幣の最小枚数を出力して改行して終了

制約
・1 ≦ n ≦ 50,000
・1 ≦ m ≦ 20
・1 ≦ 額面 ≦ 10,000
・額面はすべて異なり必ず1を含む

入力例

55 4
1 5 10 50

出力例

2

【解法】
今回は動的計画法でこちらの問題をアプローチします。

まず動的計画法とは、

下記2条件を満たすアルゴリズムの総称である。
1. 分割統治法：部分問題から問題全体を解く
2. メモ化：部分問題の計算結果を再利用する 

今回は１の分割統治ほうを用いて解法を説明する。
まず部分問題とはいわゆる数列でいう一般解のようなもので
an = an-1 +1

今回の部分問題は
T[i][j]: i番目までの紙幣を用いてj円払うときの紙幣の最小枚数
とTを定義する。

また
B[i]: 各紙幣Bの額面の配列
とBを定義する。

Tの次のTを求めると
T[i][j]に関してB[i]を使うか、使わないかの2択があり、それらの小さい値を用いる。
・B[i]を使用するパターン
　　T[i-1][j]
・B[i]を使用しないパターン
　　T[i][j – B[i]] + 1

以上より
T[i][j] = min(T[i-1][j], T[i][j – B[i]] + 1)
と部分問題を求めることができる。

答えはT[n][m]で求めることができる。

【コード】

#include <stdio.h>

void s_data(int m, int data[60000]){
  int i,j, tmp;
  for(i=0;i<m;i++){
    for(j=i+1;j<m;j++){
      if(data[i]>data[j]){
        tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
      }
    }
  }
  return;
}

int min(int a, int b){
  if(a > b){
    return b;
  }else{
    return a;
  }
}

int main(void){

  int n, m ,data[60000],i,j,count=0, T[60][60000];
  scanf("%d %d",&n,&m);
  for(i=0;i<m;i++){
    scanf("%d", &data[i]);
  }
  s_data(m, data);

  T[0][0] = 0;
  for(j=1;j<=n;j++){
    T[0][j] = T[0][j-data[0]]+1;
  }
  for(i=1;i<m;i++){
    for(j=0;j<=n;j++){
      if(j-data[i] >= 0){
        T[i][j] = min(T[i-1][j], T[i][j-data[i]]+1);
      }else{
        T[i][j] = T[i-1][j];
      }
    }
  }

  printf("%d\n", T[m-1][n]);
  return 0;
}