Python でよく使われるアルゴリズム - 貪欲アルゴリズム (別名 greedy algorithm) をご存知ですか?

貪欲アルゴリズム (または貪欲アルゴリズム) とは、問題を解決するときに、その時点で適切と思われる選択を常に行うことを意味します。つまり、全体的な最適解を考慮せずに、彼が導き出したのは、ある意味では局所的な最適解なのです。

貪欲アルゴリズムは最適な解を保証するものではありませんが、いくつかの問題では貪欲アルゴリズムの解が最適な解となります。貪欲アルゴリズムを使用して問題を計算できるかどうかを判断できる必要があります。貪欲アルゴリズムと他のアルゴリズムには明確な違いがあります。動的プログラミングでは、貪欲に選択するのではなく、常にすべてのサブ問題のソリューションを組み合わせて、現在の最適ソリューション（グローバル最適ソリューション）を取得します。バックトラッキング方式は、パスを選択しようとするものです。選択が間違っている場合は、「後悔」、つまり戻って別の選択を試すことができます。

[[280667]]

1. 変更の問題

店主が n 元のお釣りを返す必要があるとします。硬貨の額面は 100 元、50 元、20 元、5 元、1 元です。必要な硬貨の最小額を返すにはどうすればよいでしょうか? (注: 10 元という額面はありません)

お釣りが376元だったらどうなりますか？100*3+50*1+20*1+5*1+1*1=375

コードは次のとおりです。

 # tは店で入手できる小銭の額面を表します
t = [100, 50, 20, 5, 1] 
  
 # nはn元を意味します
定義変更(t, n):
 m = [範囲(len(t))内の_の場合0]
 i, money in enumerate(t)の場合:
 m[i] = n // お金 # 割り算と切り捨て
 n = n % お金 # 割り算後の余り
m, nを返す
  
 print(change(t, 376)) # ([3, 1, 1, 1, 1], 0)

2 ナップサック問題

一般的なナップサック問題には、整数ナップサック問題と部分ナップサック問題があります。問題の説明は大まかに次のようになります。

泥棒が店でn個の品物を見つけました。i番目の品物はVi元の価値があり、重さはWiキログラムです。彼はできるだけ価値の高いものを持ち帰りたいと願っていますが、彼のバックパックには最大で W キログラムの物しか入りません。どの商品を持っていくべきでしょうか？

• 0-1 バックパック: 製品の場合、泥棒はそれをそのまま持ち去るか、そのまま置いていきます。アイテムの一部だけを取ることや、同じアイテムを複数回取ることはできません（アイテムは金の延べ棒です）
• 断片的なバックパック: 泥棒は製品のどの部分でも盗むことができます。 （商品は金砂です）

例：

0-1 ナップサックと分数ナップサックの両方で、貪欲アルゴリズムは最適なソリューションを得ることができますか? なぜですか?

明らかに、貪欲アルゴリズムは、小数点付きバックパックの最適解を確実に得ることができます。各アイテムの単位重量の値を計算し、降順で並べ替えてから、アイテムの取り出しを開始します。そのタイプのアイテムがすべて入る限り、すべてを入れることができます。すべてを入れることができない場合は、バックパックがいっぱいになるまでいくつか入れることができます。

この問題に関しては、0-1 バックパックがいっぱいにならないことは明らかです。偶然可能だとしても、すべての 0-1 ナップサック問題を満たすことはできません。 0-1 ナップサック問題 (整数ナップサック問題とも呼ばれる) は、2 つのタイプに分けられます。1 つは、各カテゴリのアイテム数が制限されている (制限されている) 問題です。 1 つは無制限で、好きなだけ取得できることを意味します。貪欲な戦略は、両方に使用することはできません。 0-1 ナップサックは、整数ナップサック問題の典型的な第 1 種です。

分数バックパックコードの実装:

 # 各製品タプルは（価格、重量）を表します
商品 = [(60, 10), (100, 20), (120, 30)]
 # まず商品を並べ替える必要がありますが、もちろんここではすでに並べ替えられています
goods.sort(キー=lambda x: x[0]/x[1], 逆順= True ) 
  
 # wはバックパックの容量を表します
def fractional_backpack(商品, w):
 # mは各アイテムが何個取られたかを示します
 合計_v = 0
 m = [範囲(len(商品))内の_に対して0]
 enumerate(商品)のi、(賞品、重量)について:
 w >= 重量の場合:
 m[i] = 1
 total_v += 賞品
 w -= 重量
 # w>= weight の場合、m[i] = 1、そうでない場合はweight / w
それ以外：
 m[i] = w / 重量
 total_v += m[i]*賞金
 0 です
 壊す
m、total_vを返す
  
 res1、res2 = fractional_backpack(商品、50)
 print(res1, res2) # [1, 1, 0.666666666666666]
 1.3 最大数連結問題

n 個の非負の数値があり、文字列と同じ方法で整数に連結されます。連結して最大の整数を得るにはどうすればよいですか?

たとえば、 32、94、128、1286、6、71 を連結すると、最大の整数 94716321286128 が形成されます。

注 1:文字列のサイズの比較は、整数のサイズの比較とは異なります。文字列のサイズを比較する場合、まず最初の桁を見て、大きい方が大きな数字になります。しかし、長い文字列と短い文字列をどのように比較するのでしょうか。たとえば、128 と 1286 をどのように比較するのでしょうか。

考え方は次のとおりです。

# シンプル: 2つの等しい数値を比較すると

a = '96'  
 b = '97'   
  
 a + b、もし a > b ならば、そうでなければb + a

# 比較する桁数が等しくない場合、貪欲アルゴリズムをどのように使用すればよいでしょうか?

# 考え方を変えて文字列を連結し、結果を比較します

 a = '128'  
 b = '1286'  
 # 文字列の追加
a + b = '1281286'  
 b + a = '1286128'   
  
 a + b の場合、a + b > b + aでなければ、 b + a

デジタルスプライシングコードは次のとおりです。

 functoolsからcmp_to_keyをインポートします
  
 li = [32, 94, 128, 1286, 6, 71] 
  
 xy_cmp(x, y)を定義します。
 # 1はx>yを意味し、-1,0は同じ意味です
 x+y < y+xの場合:
戻り値1
 x+y > y+x の場合:
 -1を返す
それ以外：
 0を返す
  
定義 number_join(li):
 li = リスト(マップ(str, li))
 li.sort(キー=cmp_to_key(xy_cmp))
戻る  "" .結合(li) 
  
印刷(number_join(li)) # 94716321286128

4 活動選択の問題

同じ会場を占有する n 個のアクティビティがあるが、その会場は一度に 1 つのアクティビティのみが使用できるとします。

各アクティビティには開始時刻 Si と終了時刻 Fi (質問内の時間は整数で表されます) があり、アクティビティが間隔 [Si、fi) 内のスペースを占めることを示します。 （注：左が開いて右が閉じています）

Q: この会場で開催されるイベントの数を最大限に増やすには、どのような活動が必要ですか?

貪欲な結論:最初に終了するアクティビティは、最適なソリューションの一部である必要があります。

証明: a はすべてのアクティビティの中で最初に完了するアクティビティであり、b は最適ソリューションの中で最初に完了するアクティビティであると仮定します。

a=bの場合、結論は真である

a!=b の場合、b の終了時刻は a の終了時刻よりも遅くなければなりません。このとき、a は最適解の b を置き換えるために使用されます。a は最適解の他のアクティビティ時間と重なってはならないため、置き換え後の解も最適解です。

コードは次のとおりです。

 # タプルはアクティビティ（開始時刻、終了時刻）を表します
アクティビティ = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11),
 (8, 12), (2, 14), (12, 16)] 
  
 # アクティビティが終了時間順に並べられていることを確認します。まずは自分で並べ替えることができます。
アクティビティ.ソート(キー=lambda x:x[1]) 
  
アクティビティ選択を定義します。
 # まず、a[0]は最初に終了する必要があります
 解像度 = [a[0]]
 iが範囲(1, len(a))内にある場合:
 if a[i][0] >= res[-1][1]: # 現在のアクティビティの開始時刻が、最後に選択されたアクティビティの終了時刻以下である
 # 衝突なし
 res.append(a[i])
戻り値
  
 res = activity_selection(アクティビティ)
印刷(res)

5 最大部分列合計

最大サブ配列の合計を求める問題は、整数配列 (配列要素は負と正の両方) が与えられた場合に、連続するサブ配列の合計の最大値を求めることです。以下では、貪欲アルゴリズムを使用して 1 つずつ走査します。

コードは次のとおりです。

 def maxSubarray(li):
 s_max、s_sum = 0、0
 iが範囲(len(li))内にある場合:
 s_sum += li[i]
 s_max =最大値(s_max, s_sum)
 s_sum < 0の場合:
 s_合計 = 0 
  
 s_maxを返す