ナップサック問題を解く(貪欲法)

ナップサック問題とは、ナップサックに容量を超えずに荷物を詰めるときにその荷物の合計価値が最大となる組み合わせを求める最適化問題です。
ここでは
重さ1kg、値段100円の荷物が3個
重さ2kg、値段300円の荷物が3個
重さ5kg、値段800円の荷物が3個
ある場合に
13kgまで入るナップサックにどのように詰めれば値段が一番高くなるか
について、貪欲法で解きます。貪欲法は「重さ当たりの値段が高いものを詰めれば価値が大きくなる」という考え方で、ナップサック問題の近似解(ベストかどうかはわからないがそこそこ良い答え)を求めることができます。
Wikipedia >> 貪欲法
具体的には、荷物を重さ当たりの値段が高い順にナップザックに詰めていきます。

ナッサザック問題を解く(ライブラリknapsackを使用)

環境

windows10 home
Anaconda 3/ jupyter notebook 5.6.0
Python 3.7.0

コード

weight = [1,1,1,2,2,2,5,5,5]  # 重さ
value = [100,100,100,300,300,300,800,800,800]  # 値段
capacity = 13  # ナップサックの最大重さ

# 重さ当たりの値段の算出
v_per_w = [j/i for (i, j) in zip(weight, value)]

# 重さ当たりの値段、重さ、値段を2次元リストに
table = [v_per_w,weight,value]

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

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

# リストの列、行を入れ替え（元に戻す）
table_s = [list(x) for x in zip(*table_t)]

result_weight = []
result_value = []
total_weight = 0
total_value = 0

# 重さ当たりの値段の大きい順にループを回す
for i,j,k in zip(table_s[0],table_s[1],table_s[2]):
    #　合計重量がナップサックの最大重さを越えなければ追加
    if total_weight + j <= capacity:
        total_weight += j
        total_value += k
        result_weight.append(j)
        result_value.append(k)

# 結果の表示        
print('■値段の合計',total_value,'円')
for i,j in zip(result_weight,result_value):
    print('  重さ:',i,'kg','値段:',j,'円')
print('■重さの合計',total_weight,'kg')