AOJ2138: Vending Machine

AOJ 2138: Vending Machine (Summer Camp (Day 2), Tokyo, 13 Sep 2008)

昔DPだろうと思って突撃して死んだ問題。
今もう一度考え直してみたら、ただのBFSだと気付きました。

概要

N < 10種類のコインをそれぞれ高々 t 枚づつ使って k <= 100,000円を支払う。tを最小化せよ。

解法

N種類のコインをそれぞれ高々1枚づつ使う組み合わせは2^N通り。これを辺として、金額を頂点とするグラフ上でBFSする。
O(2^N * k). 最悪ケースで億のオーダになるけど、サーバの速さを信じて送ったらすんなり通った。
遅いけれども、コードが簡潔なので満足。

コード

#include <iostream>
#include <queue>

#define REP(i,e) for(int i=0;i<(int)(e);i++)

using namespace std;

const int N=10;
const int M=200000;
const int inf=1<<20;

int e[1<<N];

struct state{ int n,cost; };

int BFS(int n,int dst){
  static int cost[M];
  REP(i,dst+1) cost[i]=inf;

  queue<state> qu;
  for(qu.push((state){0,0});!qu.empty();qu.pop()){
    state s=qu.front();
    if(cost[s.n]!=inf) continue;
    cost[s.n]=s.cost;

    REP(i,n) if(s.n+e[i]<=dst && cost[s.n+e[i]]==inf)
      qu.push((state){s.n+e[i],s.cost+1});
  }

  return cost[dst];
}

main(){
  int n,k;
  while(cin >> n >> k && n|k){
    int v[N];
    REP(i,n) cin >> v[i];

    REP(i,1<<n){
      int cnt=0;
      REP(j,n) if(i&(1<<j)) cnt+=v[j];
      e[i]=cnt;
    }

    cout << BFS(1<<n,k) << endl;
  }

}