小銭を両替して実現する貪欲なアルゴリズム
欲張りアルゴリズムの基本的な考え方:
問題のあるステップの初期化解から与えられた目標に徐々に近づき,できるだけ早くより良い解を求める.アルゴリズムのあるステップに達してこれ以上前進できない場合,アルゴリズムを停止し,近似解を与える.
貪欲な実現過程を例に挙げて説明します.小銭を両替する例を例にしましょう.数字の額を入力して、100,50で求めます.などの額面はどのように対応するお金に両替することができます
欲張りアルゴリズムの実現過程は、上記のコードではわかりません.
問題のある初期化解から出発する
whileが設定した目標を達成(または近似達成)するかどうか
実行可能な解の1つの解の要素を求めます
すべての解要素を組み合わせて問題にする実行可能な解
このアルゴリズムにはいくつかの問題があります.
1.最後の解が最良とは保証できない
2.最値を求める質問には使用できません
3.いくつかの制約条件を満たすことしかできない実行可能な解の範囲
問題のあるステップの初期化解から与えられた目標に徐々に近づき,できるだけ早くより良い解を求める.アルゴリズムのあるステップに達してこれ以上前進できない場合,アルゴリズムを停止し,近似解を与える.
貪欲な実現過程を例に挙げて説明します.小銭を両替する例を例にしましょう.数字の額を入力して、100,50で求めます.などの額面はどのように対応するお金に両替することができます
#include
using namespace std;
void tanxin(int a);
int value[10]={10000,5000,2000,1000,500,200,100,50,20,10};
int num[10]={0};
int main(){
float t;
cout<>t;
tanxin((int)100*t);
for(int i=0;i<10;i++)
if(num[i]>0)
cout<value[i]){
break;
}
while(a>0 && i<10){
if(a>=value[i]){
a=a-value[i];
num[i]++;
}else if(a<10&&i>=5){
num[9]++;
break;
}
else
i++;
}
}
欲張りアルゴリズムの実現過程は、上記のコードではわかりません.
問題のある初期化解から出発する
whileが設定した目標を達成(または近似達成)するかどうか
実行可能な解の1つの解の要素を求めます
すべての解要素を組み合わせて問題にする実行可能な解
このアルゴリズムにはいくつかの問題があります.
1.最後の解が最良とは保証できない
2.最値を求める質問には使用できません
3.いくつかの制約条件を満たすことしかできない実行可能な解の範囲