2138 - Vending Machine

AOJ
問題

N種類のコインを使ってm円のお釣りを支払う。
違う種類のコインなら1つの操作で支払うことが出来る。
このとき操作の最小回数を求めよ。

制約

N<=10
M<=100000

解法

1回の操作での支払い方は2^N通りある。
2^N種類のコインがある場合の普通のお釣りDPをすればいい。
計算量はO(2^N*M)で怪しいかと思ったけど普通に通った。

ソース
int v[1<<10];
int dp[100001];

int main() {
  int n,m;
  while(cin>>n>>m,n||m) {
    int a[n];
    REP(i,n) cin >> a[i];
    REP(S,1<<n) {
      int s=0;
      REP(i,n) if (S>>i&1) s+=a[i];
      v[S]=s;
    }
    REP(i,m+1)dp[i]=INF;
    dp[0] = 0;
    for (int S=1; S<(1<<n); ++S) {
      for (int i=0; i+v[S]<=m; ++i)
        dp[i+v[S]] = min(dp[i+v[S]], dp[i]+1);
    }
    cout << dp[m] << endl;
  }
}