2_貪欲法

Tweet

貪欲法ってなに

貪欲法とは、局所探索法の一つ。
ナップサック問題の各荷物の評価値を「（価値）÷（容積）」で決定しする。
評価値の一番高い荷物を選び、最大容量に収まるようにナップサックに入れる。
全ての荷物を評価値の順に選び上記の操作を繰り返す。

つまり？

ざっくり書くと、荷物ごとに「（価値）÷（容積）」で評価値を出し、
容量超えないように、評価値順に荷物を入れていく。
計算量もかなり少なく済みそう。

早速書いてみた

ってことで、さっそく書いてみた。

コード

# 変数の宣言
result_size = []
result_price = []
total_size = 0
total_price = 0
combi = []

#物の重さ、価値
size = [10, 12, 7, 9, 21, 16]
price = [120, 130, 80, 100, 250, 185]

# 要領
capacity = 65

# 重さ当たりの値段を算出
price_per_size = [j/i for(i,j)in zip(size,price)]

# 重さ当たりの値段,重さ,値段を2次元リストにする
table = [price_per_size,size,price]

# リストの列,行を入れ替え
table_t = [list(x) for x in zip(*table)]

# 重さ当たりの値段を使って降順にソートする
table_t.sort(reverse= True)

# リストの列,行を元に戻す
table_s = [list(x) for x in zip(*table_t)]

# 重さあたりの値段の大きい順にループする
for i,j,k in zip(table_s[0],table_s[1],table_s[2]):
    if total_size + j <= capacity:
        total_size += j
        total_price += k
        result_size.append(j)
        result_price.append(k)
        combi.append(j)

# 結果の表示
print("合計が最大になる組み合わせ")
print(combi)
print("合計価格: ", total_price)
print("合計サイズ: ", total_size)

出力

...あれ、なんか総当たりの時と値が違う。
ここで比較画像

答えに近いけど、最適ではないんだね。

参考：https://tat-pytone.hatenablog.com/entry/2019/06/04/202452

この方法の欠点

実はこの「貪欲法」は、近似解を求めるのに使う。
なので、最適解を求める問題には向いてない。
(まあ、ざっくり答えを出したい時とかは向いてそう)
ここで、新しい方法を試してみる。