PythonのPuLPでナップザック問題を解く - 気ままに技術勉強ブログ

今回はPythonのPuLPでナップザックを解いてみようかと思います。

PuLPとは数理最適化の問題を解くためのライブラリであり、このライブラリを使うととても簡単な記述で数理最適化の問題を解くことができるようになります。

そのPuLPで問題設定をい記述する際にいくつか推奨、非推奨な書き方があるようでして、下記のサイトに書かれています。

qiita.com

抜粋すると、、、

変数はpulp.LpVariablle.dictsで作成する
式の表現はlpSumを使う（lpDotは使わない）
自作で変数のリストは作らない
LpVariable.matrixは使わない

そこで、上のサイトに書かれている書き方に慣れるため、簡単な数理最適化に関する問題をPuLPで解いていこうと思います。

解く問題は下記サイトの中のナップザック問題です。（ここのサイトは様々なサンプル問題とその解き方が載っていて、毎回とても参考にさせていただいてます）

www.nct9.ne.jp

今回解く問題について

下表に示す品物をサイズ 15 のナップザックに入れるとき、金額が最大となる入れ方を求めてください。

品物	金額	サイズ
a	4	3
b	5	4
c	6	5
d	8	7
e	10	9

コード

以下が実際に書いてみたコードです。いつものようにコードに関する説明はありませんが、トリッキーな記述は無いので難しくはないかと思います。

[In]

# 必要となるライブラリをimportします。
import pulp
import pandas as pd

[In]

# 品物や金額のDataFrameを作成
df = pd.DataFrame(
    data={"品物": ["a", "b", "c", "d", "e"], 
          "金額": [4, 5, 6, 8, 10],
          "重さ": [3, 4, 5, 7, 9]
         }
)
df = df.set_index("品物")  # "品物"をインデックスに割り当てる
df

[Out]

	金額	重さ
品物
a	4	3
b	5	4
c	6	5
d	8	7
e	10	9

# LpVariable.dictsを使って変数を作成
x = pulp.LpVariable.dicts("item", df.index, cat=pulp.LpBinary)
x

[Out]

{'a': item_a, 'b': item_b, 'c': item_c, 'd': item_d, 'e': item_e}

[In]

# 目的関数や制約を記述
problem = pulp.LpProblem(name="knapsack", sense=pulp.LpMaximize)

problem += pulp.lpSum([df["金額"][i] * x[i] for i in x.keys()])

problem += pulp.lpSum([df["重さ"][i] * x[i] for i in x.keys()]) <= 15
problem

[Out]

knapsack:
MAXIMIZE
4*item_a + 5*item_b + 6*item_c + 8*item_d + 10*item_e + 0
SUBJECT TO
_C1: 3 item_a + 4 item_b + 5 item_c + 7 item_d + 9 item_e <= 15

VARIABLES
0 <= item_a <= 1 Integer
0 <= item_b <= 1 Integer
0 <= item_c <= 1 Integer
0 <= item_d <= 1 Integer
0 <= item_e <= 1 Integer

[In]

# 求解
status = problem.solve(pulp.PULP_CBC_CMD(msg=0))
print("Status", pulp.LpStatus[status])

[Out]

Status Optimal

[In]

# 結果を出力
print(problem.objective.value())
print(df.index.tolist())
print([x[i].value() for i in x])

[Out]

18.0
['a', 'b', 'c', 'd', 'e']
[1.0, 0.0, 1.0, 1.0, 0.0]

終わりに

今回は以上です。PuLP楽しいー！！