貪欲なアルゴリズムの基本的なアイデア
1.問題を説明するために数学モデルを確立します。
2。解決された問題をいくつかのサブ問題に分けます。
3.各サブ問題を解決し、サブ問題に対するローカル最適ソリューションを取得します。
4.サブ問題の局所的な最適なソリューションを、問題の元の解決策のソリューションに合成します。
このアルゴリズムを実装するプロセス：
問題に対する特定の最初の解決策から始まります。
一方、特定の全体的な目標に進むことができます
実行可能なソリューションのソリューション要素を見つけます。
問題に対する実行可能な解決策は、すべてのソリューション要素で構成されています。
貪欲な選択的性質
いわゆる貪欲な選択の性質は、あなたが探している問題の全体的な最適な解決策は、一連のローカルな最適な選択を通じて達成できることを意味します。それを考慮せずに現在の問題。これは、貪欲なアルゴリズムの実現可能性の最初の基本要素です。
貪欲なアルゴリズムは、繰り返し貪欲な選択をし、貪欲な選択が行われるたびに、あなたが探している問題はより小さなサブ問題に減らされます。
特定の問題のために、それが貪欲な選択の性質を持っているかどうかを判断するために、各ステップで行われた貪欲な選択が最終的に問題に対する全体的な最適な解決策につながることを証明する必要があります。
2。最適な下部構造特性<Br />問題の最適解にそのサブ問題の最適解を含む場合、この問題は最適なサブ構造特性を持つと言われています。問題の最適な下部構造性は、貪欲なアルゴリズムによって解決できる重要な機能です。
貪欲の一般的なプロセス
コードコピーは次のとおりです。
greedy（c）// cは問題の入力セット、つまり候補セットです
{
s = {}; //初期ソリューションセットは空のセットです
一方（ソリューションではありません）//セットSは問題の解決策を構成しません
{
x = select（c）;
実行可能な場合（s、x）//セットsにxを追加した後の解決策が実行可能かどうかを判断します
s = s+{x};
c = c- {x};
}
s;
問題の説明：
現在、2 jiao 5セント、1 jiao 5セント、5セント、1セントのコインがあります。
問題分析：
常識によれば、私たちが物を買ってお金を見つけるために店に行ったとき、上司は常に最大の宗派を与えてください。上司がスコアまたは数セントを求めている場合、あなたは間違いなくそれをしないでしょう。実際、これは貪欲な選択の典型的な問題です。
アルゴリズムの設計と問題の実装：
最初に例を挙げてみましょう。彼はこのようにそれを探しますか？ 'Tそれをする、それから上司は私に35ポイントを得ただけで24回与えられたので、24ポイントを与えられたので、10ポイントと4ポイントを与えなければなりませんでした。
コードコピーは次のとおりです。
//変更を見つけるための算術
//入力：配列M、順番に配置された面面の数を保存します。
//出力：配列num、配列Mの異なる宗派値を持つコインの数を比較し、マネープランを見つけます
public static int [] zhaoqian（int m []、int n）
{
int k = m.length;
int [] num = new int [k];
for（int i = 0; i <k; i ++）
{
num <i> = n/m <i>;
n = n％m <i>;
}
numを返します。
}
コードコピーは次のとおりです。
パブリッククラスZhaoqian
{
public static void main（string [] args）
{
int m [] = {25,10,5,1};
int n = 99;
int [] num = new int [m.length];
num = zhaoqian（m、n）;
System.out.println（n+"マネーファインディングプラン："）;
for（int i = 0; i <m.length; i ++）
System.out.println（num <i>+"zip"+m <i>+"額面"）;
}
public static int [] zhaoqian（int m []、int n）
{
int k = m.length;
int [] num = new int [k];
for（int i = 0; i <k; i ++）
{
num <i> = n/m <i>;
n = n％m <i>;
}
numを返します。
}
}
上記はこの記事のすべての内容です。あなたがそれを好きになることを願っています。