ダブル11プロモーション？貪欲アルゴリズムを使用して解決してください。

[[351760]]

この記事はWeChatの公開アカウント「Java Chinese Community」から転載したもので、著者はLei Geです。この記事を転載する場合は、Java Chinese Community 公式アカウントにお問い合わせください。

近年、企業は消費を刺激するためにさまざまな活動を展開しており、Duoduoを筆頭とする実用的電子商取引企業は、マーケティングの無限の「可能性」を私たちに見せてくれました。

つい最近、ダブル11に合わせて、近所のコンビニの老旺頭も「ワインの空き瓶をワインに」というプロモーションを開始しました。そのルールは次のとおりです。

この記事は Github の「初心者のためのアルゴリズム」シリーズに含まれています: https://github.com/vipstone/algorithm

活動ルール

顧客がワインを X 本購入した場合、空のボトル ​​Y 本を新しいワイン 1 本と交換できます。

ヒント：
 XとYの値は次のとおりです。
 1 <= X <= 100
 2 <= Y <= 100
 Y 値は固定されておらず、ランダムに選択されます。

ボトルの中のワインが飲まれると、ボトルは空になります。

最大で何本のワインを飲めるか計算してください。

例1:

入力: X = 9、Y = 3
出力: 13
説明: 空のワインボトル 3 本をワインボトル 1 本と交換できます。したがって、飲めるボトルの最大数は 9 + 3 + 1 = 13 です。

例2:

入力: X = 15、Y = 4
出力: 19
説明: 空のワインボトル 4 本をワイン 1 本と交換できます。したがって、飲めるボトルの最大数は 15 + 3 + 1 = 19 です。

例3:

入力: X = 5、Y = 5
出力: 6

例4:

入力: X = 2、Y = 3
出力: 2

問題解決

この問題には 2 つの難点があります。1 つ目は、ワイン 1 本と交換される空のボトルの数は固定されていない (ランダムである) ことです。2 つ目は、交換したワインを飲んだ後も、交換活動に参加し続けることができることです。したがって、この 2 つの条件を満たすことを前提として、最大で何本まで飲めるかを計算します。

この記事のタイトルを見て、問題の解決法が分かった方もいるかもしれません。そうです、この記事では「貪欲アルゴリズム」を使用して最終的な答えを計算します。同時に、この問題は貪欲アルゴリズムの解決アイデアにも準拠しています。つまり、ワインボトルがあれば、それを交換でき、できるだけ多く交換できます。

貪欲アルゴリズム

貪欲アルゴリズムは、各ステップで現在の状態における最良または最適な（つまり、最も好ましい）オプションを選択し、結果が最良または最適なものになることを期待するアルゴリズムです。

貪欲アルゴリズムは、最適なサブ構造を持つ問題で特に効果的です。最適なサブ構造とは、ローカル最適解がグローバル最適解を決定できることを意味します。簡単に言えば、問題は解決すべきサブ問題に分解することができ、サブ問題に対する最適解は、最終的な問題に対する最適解に再帰的に導き出されます。

貪欲アルゴリズムの実装フレームワーク

問題の初期解決から始めます:

（与えられた全体目標に向かって一歩を踏み出せる）

{

実行可能な決定を使用して、実行可能なソリューション要素を見つけます。

}

すべてのソリューション要素が組み合わされて、問題に対する実行可能なソリューションが実現されます。

注意: 貪欲アルゴリズムは、ローカル最適解戦略を解くことによってのみグローバル最適解を達成できるため、問題が貪欲アルゴリズム戦略に適しているかどうか、および見つかった解が間違いなく問題に対する最適解であるかどうかに注意する必要があります。

次に、コードを使用して貪欲アルゴリズムの具体的な実装を示します。

コード実装1: 貪欲

まず、グローバルな問題をローカルな問題に変換してみましょう。空のボトルをワインのボトルと交換できる場合は、それをワインのボトルと交換します。実装コードは次のとおりです。

 // 貪欲法 1: + と - で実装
クラスソリューション{
公共  int numWaterBottles( int numBottles, int numExchange) {
        // ボトルの最大数
int合計 = numBottles;
        // ワインのボトルをお持ちの場合は交換してください
        (ボトル数 >= 交換数) {
            //償還ラウンドを実行する
            numBottles -= numExchange;
            ++合計;
            // 交換ごとにワインを 1 本追加
            ++ボトル数;
        }
合計を返します。
    }
 }

コード分​​析

実装のアイデア:

1. まずワインを全部飲みます int total = numBottles;
2. 空のボトルが十分にある場合は、それをワインのボトルと交換し、while ループを実行します。
3. サイクルでは、空のボトルの数 +1、飲める飲み物の数 +1。
4. 次のループ判定を実行します。

上記のコードを LeetCode に送信すると、実行結果は次のようになります。

コード実装2: 貪欲な改善

上記の貪欲アルゴリズムは、1 サイクルで一度に 1 本のワインを交換するというものです。毎回、すべての空のボトル ​​(交換可能な最大値) を交換し、交換したワインを飲んでから、再度交換することは可能でしょうか。

答えは「はい」です。これを実現するには、剰余演算と剰余演算を使用するだけです。具体的なコードは次のとおりです。

 // 貪欲 2: / と % で実装
クラスソリューション{
公共  int numWaterBottles( int numBottles, int numExchange) {
        //ボトルの総数
int合計 = numBottles;
        // ワインのボトルをお持ちの場合は交換してください
        (ボトル数 >= 交換数) {
            // 交換できる新しいワインの最大量
int n = numBottles / numExchange;
            // ボトル合計数
            合計 += n;
            // 残りのボトル（未使用のボトル＋使用済みで飲んだボトル）
            numBottles = numBottles % numExchange + n;
        }
合計を返します。
    }
 }

上記のコードを LeetCode に送信すると、実行結果は次のようになります。

要約する

貪欲アルゴリズムは一見すると非常に「難しい」ように見えますが、実際には実装が非常に簡単です。実は、「アルゴリズム」についても同じことが言えます。一見すると、この言葉はあまり高尚な響きではないようです。実際、それは問題を解決するための単なるアイデアであり、固定された「ルーチン」であり、そこには何も神秘的なところはありません。

人々はよくこう言います。「道は遠くても、最終的には目的地にたどり着くだろう。仕事は困難でも、最終的には成功するだろう。」 「難しい」と「簡単」は常に相対的です。実際、「難しい」から「簡単」になるのは、徐々に悟りと成長を遂げるプロセスです。

毎日少しずつ成長していくことを願っています。最後に、私個人のWeChat: GG_Stoneを残してください。お互いにコミュニケーションを取り、一緒に進歩していくことができるように。

参考文献と謝辞

https://leetcode-cn.com/problems/water-bottles/

https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html

https://zh.wikipedia.org/zh-hans/貪欲アルゴリズム