2007-Make Purse Light
考え方
全ての支払い方を調べる。
「出した硬貨と同じ種類の硬貨が釣り銭として戻ってくるような払いかた」を避けるために、同じ枚数になる支払い方がある場合は合計金額が最も小さい物を選ぶ必要がある。
実装(C++)
int value; int v[4]={500,100,50,10}; int c[4]; //k円出す時の最小の枚数 int change(int k){ int res=0; for(int i=0;i<4;i++){ while(k>=v[i])k-=v[i],res++; } return res; } int mincount,minsum; int r[4]; int t[4]; //a番目のコインを用いる。利用した枚数がb。 void dfs(int a,int b,int sum){ if(a==4){ if(sum<value)return; int count=change(sum-value)-b; if(count<mincount||(count==mincount&&minsum>sum)){ minsum=sum; mincount=count; for(int i=0;i<4;i++) r[i]=t[i]; } }else{ for(int i=0;i<=c[a];i++){ t[a]=i; dfs(a+1,b+i,sum+v[a]*i); } } } int main(){ int s=0; for(;;){ cin>>value; if(value==0)break; if((s++)>0)cout<<endl; for(int i=3;i>=0;i--) cin>>c[i]; mincount=minsum=INT_MAX; dfs(0,0,0); for(int i=3;i>=0;i--){ if(r[i]>0){ cout << v[i] << " " << r[i] << endl; } } } return 0; }