ナップザック問題を貪欲法で解いたメモ

ナップザック問題を貪欲法で解いた際のメモです。

貪欲法の方針

容積あたりの価値が大きいものを先にナップザックに入れて、入り切ったものが解！
というのが、ナップザック問題の貪欲法における方針です。
例えば、過酷なサバイバルの準備のために、どちらも容積がほとんど同じである「うま〇棒」と「〇本満足バー」を好きなだけナップザックに詰めて持っていけるのなら、ナップザックいっぱいに「〇本満足バー」だけを詰め込むでしょう。そういうヒューリスティックに基づいています。

実装についてのメモ

１つの品物に１つのタプル（品物,価値,容積）を割り当て、それをリストで保持する方法が個人的に便利だと思います。
つまり、リストは次のような具合になります。

tuples = [
(品物,価値,容積),
(品物,価値,容積),
　　　 :
(品物,価値,容積)
]

リスト内のタプルの要素にアクセスするとき、例えば、

品物"3"の"容積"

にアクセスするときは

tuples[2][2]

で値を取得できます。

コード

knapsack_greedy.py

import numpy as np

C = 2             #ナップザックの大きさ
len = 10          #品物の数
tuples = []       #（インデックス、価値、重さ、価値/重さ）を保持するリスト

#貪欲法の解とその初期化
sol = np.zeros(10)

#価値と重さの初期化
values = np.random.rand(len)
costs = np.random.rand(len)


#（インデックス、価値、容積、価値/容積）
for i in range(len):
    tuples.append((i,values[i],costs[i],float(values[i]/costs[i])))

#ソート後のタプル
tuples_sorted = []

#価値/容積の順で、ソートする
for x,y,z,w in sorted(tuples,key=lambda x:x[3],reverse = True):
    tuples_sorted.append((x,y,z,w))

sum = 0         #代入用変数    

for i in range(len):
    #容積あたりの価値が大きい物からナップザックに入れていく
    sum+=tuples_sorted[i][2]
    if(sum < C):
        sol[tuples_sorted[i][0]]=1         #容量オーバーしないなら入れる
    else:
        sol[tuples_sorted[i][0]]=0         #容量オーバーするので入れない

print("ナップザックの大きさ"+str(C))
print("価値")
print(np.round(values,3))
print("重さ")
print(np.round(costs,3))
print("選んだ品物")
print(sol)

sum_ = 0
for i in range(len):
    sum_ += sol[i]*costs[i]

print("選んだ品物の総容量")
print(str(sum_))

出力

ナップザックの大きさ2
価値
[ 0.631  0.543  0.668  0.337  0.011  0.454  0.536  0.527  0.434  0.833]
重さ
[ 0.823  0.546  0.759  0.028  0.005  0.638  0.694  0.468  0.474  0.351]
選んだ品物
[ 0.  1.  0.  1.  1.  0.  0.  1.  1.  1.]
選んだ品物の総容量
1.87266067297