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

ナップサック問題とは、ナップサックに容量を超えずに荷物を詰めるときにその荷物の合計価値が最大となる組み合わせを求める最適化問題です。
ここでは
重さ1kg、値段100円の荷物が3個
重さ2kg、値段300円の荷物が3個
重さ5kg、値段800円の荷物が3個
ある場合に
13kgまで入るナップサックにどのように詰めれば値段が一番高くなるか
について解きます。ライブラリ'ortoolpy'の'knapsack'を用います

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

環境

windows10 home
Anaconda 3/ jupyter notebook 5.6.0
Python 3.7.0

準備

ライブラリortoolpy をpipでインストールします。

pip install ortoolpy

コード

from ortoolpy import knapsack

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

# ナップサック計算
result = knapsack(weight, value, capacity)

# 結果表示
print('■値段の合計',result[0],'円')
total = 0
print('■組み合わせ')
for i in result[1]:
    print('  重さ:',weight[i],'kg','値段:',value[i],'円')
    total += weight[i]
print('■重さの合計',total,'kg')