小銭を探す問題(C言語実現)——貪欲アルゴリズム応用(1)

現実の生活では、20,10,5,1の硬貨の数に限りがないと仮定して、おつりを探す問題がよくあります.
小銭を探す必要があることを与えて、小銭を探す方案を求めて、要求:使用数の最も少ない硬貨.
このような問題に対して、欲張りアルゴリズムは、お金を探すときに、いつもお金を探すことができるコインの最大値を選択する方法を採用しています.例えば、おつりの数が25の場合、おつりの仕方は10+10+5ではなく20+5です.

#include
using namespace std;
void greedMoney(int m[],int k,int n){
	int i;
	for( i=0;i=m[i]){
			cout<

説明する必要があるのは、場合によっては、小銭問題が貪欲アルゴリズムを用いて全体的な最適解を得ることができず、その結果は最適解の良好な近似にすぎない可能性がある.
たとえば、11,5,1,15の値を指定するとします.
欲張りアルゴリズムを使ってお釣りを探す方式は11+1+1+1で、5枚の硬貨が必要です
最適解は5+5+5で、コインは3枚しか必要ありません.
 
まとめ:おつりの問題についての考え方は、
一、小銭の額面額を配列に並べ替える.
二、最大額面から比較して、額面が0であることがわかるまで.