Pythonでは、ナップザック問題のような最適化問題を簡単に解くことができるライブラリがいくつか用意されています。
今回は、『PuLP』『knapsack』『cvxpy』の3種類それぞれで実装してみました。
ナップザック問題とは、どういうものなのか。
ナップザック問題ってPythonのライブラリを使えば、
こんなに簡単に解くことができるかを知ってもらえたらと思ってます。
Contents
ナップサック問題とは
最適化問題の一つ。
問題の概要は以下の通りです。
荷物が N 個ある
各 i に対して、i 番目の荷物は重さが wi、価値が vi
ナップサックには合計重さ W までしか荷物が入らない
荷物をナップサックにうまく入れて、価値を最大化したい
要は、制約条件ある中でもっとも最適な組み合わせは何かということを求める問題です。
ナップサック問題の定式化
ナップサックの容量と荷物を決める
ナップサック問題と調べると最も表示される、この画像の通りに実装します。
ナップザックの容量は、15kg。
荷物は、5つ。
| # | 価値 | 重さ |
| 0 | $4 | 12kg |
| 1 | $2 | 2kg |
| 2 | $2 | 1kg |
| 3 | $1 | 1kg |
| 4 | $10 | 4kg |
ナップサック問題を解く式
なんか難しそう。
でも、実際は簡単です。後ほど実装を見ていきましょう！
ナップサック問題の答え
まずは、結論から言うと上記の問題の答えは、
15kgという制約の中で0と3と4を選んだ時に価値が最大化し、$17となります。
では、実際に実装を見ていきます。
ナップサック問題をPuLPで解く
PuLPのインストール方法
pipでインストールします。
anacondaの方は、pipをcondaに変えてください。
jupyter notebookでやられる方は、pipの前に!をつけましょう。
pip install pulpPuLPで実装
まず、pulpをインストール。
重さや価値、ナップザックの許容量を定義。
変数を定義します。
変数というのが、今回ナップザックに入れる商品になります。
from pulp import *
# 重さ
w = [4, 2, 2, 1, 10]
# 価値
v = [12, 2, 1, 1, 4]
# 制約：15kg
W = 15
r = range(len(w))
# 数理モデル
m = LpProblem(sense=LpMaximize)
# 変数
x = [LpVariable('x%d'%i, cat=LpBinary) for i in r]
# 目的関数
m += lpDot(v, x)
# 制約
m += lpDot(w, x) <= W m.solve() print('最大価値:{} / 組み合わせ:{}'.format(value(m.objective), [i for i in r if value(x[i]) > 0.5]))PuLPの結果
最大価値:17.0 / 組み合わせ:[0, 3, 4]ナップサック問題をKnapsackで解く
ortoolpyという、オペレーションリサーチ用のライブラリの1機能としてナップザック問題に適したメソッドが利用できます！
Knapsackのインストール方法
pipでインストールします。
anacondaの方は、pipをcondaに変えてください。
jupyter notebookでやられる方は、pipの前に!をつけましょう。
pip install ortoolpyKnapsackの実装
まず、ortoolpyからknapsackをインストール。
あとは、knapsackに定義した重さや価値、ナップザックの許容量を与えてあげるだけです。
from ortoolpy import knapsack
# 重さ
w = [4, 2, 2, 1, 10]
# 価値
v = [12, 2, 1, 1, 4]
# 制約：15kg
W = 15
result = knapsack(w, v, W)
print('最大価値:{} / 組み合わせ:{}'.format(result[0], result
))Knapsackの結果
最大価値:17.0 / 組み合わせ:[0, 3, 4]ナップサック問題をcvxpyで解く
上記のサイトを参考にさせていただきました。
ただ、cvxpyのバージョンがあがったためか、
参考させていただいたソースコードでは動きませんでした。
なので、最新バージョンに合わせた実装に変えております。
cvxpyのインストール方法
pipでインストールします。
anacondaの方は、pipをcondaに変えてください。
jupyter notebookでやられる方は、pipの前に!をつけましょう。
pip install cvxpycvxpyの実装
重さや価値、ナップザックの許容量は同じです。
PuPLと同じように変数を定義します。
PuPLと違うのは、数理モデルと目的関数を同時宣言するところです。
from cvxpy import *
# 重さ
w = [4, 2, 2, 1, 10]
# 価値
v = [12, 2, 1, 1, 4]
# 制約：15kg
W = 15
# 変数
x = cvxpy.Variable(shape=len(v), boolean=True)
# 目的関数
objective = cvxpy.Maximize(v * x)
# 制約
constraints = [W >= w * x]
prob = cvxpy.Problem(objective, constraints)
prob.solve(solver=cvxpy.ECOS_BB)
print('最大価値:{} / 組み合わせ:{}'.format(round(prob.value, 0), [i for i in range(len(v)) if round(x.value[i], 0) == 1]))cvxpyの結果
最大価値:17.0 / 組み合わせ:[0, 3, 4]cvxpyの場合、少数で結果がでます。そのため、四捨五入して整数化しています。
ナップサック問題を解いてみた感想
最もシンプルに実装できるのはnapsackですね、
ナップサック問題に特化したライブラリなので、当然といえば当然ですが。
最適化問題は、多く分野で使われる内容なのでしっかりと身に付けたい内容ですね。
