【C++】貪欲法

貪欲法

・単純な硬貨問題
任意の標準入力から出力された値で硬貨の合計枚数を最小限にしたい場合、何枚になるか？

#include <iostream>

using namespace std;

int main(){
    int x;
    cin >> x;
    
    int coin[] = {500,100,50,10,5,1,};
    int count =0; 
    
    for (int i = 0; i < 6; i++){
        count += x / coin[i];
        x %= coin[i];
    }
     cout <<count << endl; 
        return 0;
}

解法と感想

貪欲法の解き方→大きい変数の値から降順に使用していく
今回の場合は硬貨なので6種類の硬貨の各値を使用

int coins = {500, 100, 50, 10, 5, 1};
coinsに各種硬貨を配列で組み込む

繰り返し処理で最小の硬貨枚数になるまで実行する

for (int i = 0; i < 6; i++) {
    count += X / coins[i];  // その硬貨をできるだけ使う
    X %= coins[i];          // 残りの金額を更新
}

int=i 初期値＝0。
i < 6;で各硬貨で割り切れる枚数までiを増加させる

X / coins i　で何枚硬貨が使えるのか判定する
X %= coins[i];で残り金額を更新していく

▼感想
・実際にはこの貪欲法にデータ処理の形を落とし込む機会がありそう
・貪欲法の場合、まずカウンタ変数内に設定する値で入力値が最適に割り出せるのかも重要になってくる。
・硬貨のように最適解が出せるデータ処理体系があれば使用できるが、経路探索などの最短経路が常に最適な処理であるとは限らない場面では使用に適さない。