貪欲法

一つのルールに従ってその場での最善を選ぶアルゴリズムの設計原理。

硬貨の問題

{1,5,10,50,100,500}のコインがあってコインの枚数がc1,c2,c3,c4,c5に別々に設定されている。
Aの金額を払うときコインの枚数を一番少なく出す方法を探そう。

入力例 : c={3,2,1,3,0,2} A=620

コード

#include <iostream>
using namespace std;
const int V[6]={1,5,10,50,100,500};
int C[6]={3,2,1,3,0,2};
int A=620;
void solve(){
    int ans=0;
    for(int i=5;i>=0;i--){
        int t=std::min(A/V[i],C[i]);
        std::cout<<"["<<t<<"] ["<<V[i]<<"]"<<std::endl;
        std::cout<<A<<" - "<<t*V[i]<<" = ";
        A-=t*V[i];
        std::cout<<A<<std::endl;
        //Aを一番大きいからコインで割ったものとコインの枚数のどっちが小さいか
        //比較して小さいほうとコインをかけてAへ引き算する。
        ans+=t;
    }
printf("%d\n",ans);
}
int main(){
    solve();
}

実行結果

[1] [500]
620 - 500 = 120
[0] [100]
120 - 0 = 120
[2] [50]
120 - 100 = 20
[1] [10]
20 - 10 = 10
[2] [5]
10 - 10 = 0
[0] [1]
0 - 0 = 0
6