貪欲アルゴリズムとは何ですか？

貪欲なアルゴリズムは、 アルゴリズム設計における手法の一つです。

各段階で局所最適を選択することで、全体最適に到達することが期待されます。

結果は常に最適とは限りません

取引所を変更

硬貨は使用可能な異なる額面の硬貨、変動額は交換される合計額、合計額に対して交換可能な硬貨の最小枚数を求めます。

ビスケットの配布

局所最適化：最も少ない消費量で子どもを満足させます。小さいビスケット」は「食欲が最も小さい」子供に最初に与えられます。アルゴリズムのステップ

• 1.まず、ビスケットの配列と食欲の配列を昇順に並べ替えます。
• 2.ビスケットの配列を繰り返し、最初の子を満たすビスケットを探します。
• 3. 次に、ビスケットの配列を走査して、2番目、3番目...を満たすクッキーを見つけます。ビスケットのn個の子

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
 const sortFunc = function(a, b){
 return a - b;
 }
 g.sort(sortFunc);
 s.sort(sortFunc);
 let i = 0;
 s.forEach(function(n){
 if(n >= g[i]){
 i++;
 }
 })
 return i;
};

株の買い時と売り時II（パワーボタン122）

前提条件：神の視点と将来の価格に関する知識。局所最適：長期的な計画を立てることなく、良いものは悪いものと一緒に、悪いものは悪いままにしておきます。アルゴリズムのステップ：

• 1、利益の合計をカウントするための新しい変数
• 2、価格の配列をトラバース、現在の価格は昨日よりも高い場合は、昨日購入し、今日販売し、それ以外の場合は取引なし
• 3、トラバーサルの終わり、すべての取引利益の合計に戻ります。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
 let profit = 0;
 for(let i = 1; i<= prices.length; i++){
 if(prices[i] > prices[i-1]){
 profit += (prices[i] -prices[i-1]);
 }
 }
 return profit;
};

知識ソース：