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

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

[[351760]]

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

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

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

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

活動ルール

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

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

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

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

例1:

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

例2:

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

例3:

  1. 入力: X = 5、Y = 5
  2. 出力: 6

例4:

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

問題解決

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

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

貪欲アルゴリズム

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

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

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

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

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

{

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

}

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

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

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

コード実装1: 貪欲

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

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

コード分​​析

実装のアイデア:

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

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

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

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

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

  1. // 貪欲 2: / と % で実装
  2. クラスソリューション{
  3. 公共  int numWaterBottles( int numBottles, int numExchange) {
  4. //ボトルの総数
  5. int合計 = numBottles;
  6. // ワインのボトルをお持ちの場合は交換してください
  7. (ボトル数 >= 交換数) {
  8. // 交換できる新しいワインの最大量
  9. int n = numBottles / numExchange;
  10. // ボトル合計数
  11. 合計 += n;
  12. // 残りのボトル(未使用のボトル+使用済みで飲んだボトル)
  13. numBottles = numBottles % numExchange + n;
  14. }
  15. 合計を返します
  16. }
  17. }

上記のコードを 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/貪欲アルゴリズム

<<:  家主は、あなたに賃貸するかどうかを決める前に、AIを使ってあなたの犯罪歴を審査しているかもしれない。

>>:  独身の日:XiaoIceの「バーチャルガールフレンド」が正式にリリースされ、複数のプラットフォームで使用可能に

ブログ    
ブログ    

推薦する

Llama 2を完全に置き換えます!白川2は歴史上最も完全なトレーニングの詳細を明らかにする

この国では、ラマの時代は終わった。 9月6日、百川知能は7Bと13Bのベースとチャットバージョンを含...

AIエンタープライズアプリケーションは成熟しつつある

デロイトは最新の「企業における AI の現状」レポートで、AI 実践の成功を特徴付ける共通点と、達成...

人工知能は企業で実用化されつつある

AI は、従来のプロセスや従来のテクノロジーにまき散らされた魔法の精霊ではなく、ビジネスのやり方を根...

...

...

...

WPS AIは正式に公開され、WPSスマートドキュメントに初めて適用されました。

9月5日、Kingsoft OfficeはWPS AIを正式に公開したと発表しました。AI機能はま...

「AI顔変換」技術の悪用はサイバーセキュリティ詐欺の氷山の一角を露呈

今年に入ってからは、ChatGPTやGPT-4などの技術の応用により、深層合成製品やサービスが増加し...

...

人工知能プロジェクトからビジネス価値をうまく引き出すための 8 つの秘訣

[[249778]] AI はビジネスに大きな可能性を秘めていますが、ほとんどの組織がそのメリットを...

顔認識技術が「無人小売」時代の到来を牽引

序文:顔認識は現在最も人気のある人工知能技術として、生産と生活のあらゆる側面で広く使用されています。...

1万語に及ぶ長い記事です!ディープマインドの科学者が2021年の高エネルギー研究15件をまとめる

2021 年には、より強力なコンピューティング能力、データ、モデルの助けを借りて、機械学習と自然言語...

機械学習の実践: Spark と Python を組み合わせるには?

Apache Sparkはビッグデータの処理や活用に最も広く使われているフレームワークの一つであり...

ドローン自動化システムの産業への応用を探る

世界中の企業は、競合他社に対して競争上の優位性を獲得するのに役立つ高度なテクノロジーを常に探していま...

人工知能と医療画像を組み合わせたアプリケーションの4つのコア価値

「人工知能+医用画像」は、最先端の人工知能技術を医用画像診断に適用し、医師が患者の状態を診断するのを...