ナップサック問題 PuLP

ナップサック問題

PuLPを使用してナップサック問題を解いてみます。

例題:

🔹ナップサックの容量：15
🔹商品A: 価値10, 重さ5
🔹商品B: 価値12, 重さ6
🔹商品C: 価値8, 重さ3
🔹商品D: 価値15, 重さ7
🔹商品E: 価値4, 重さ2

このナップサック問題では、15の容量を持つナップサックに、価値と重さが異なる5つの商品を詰め込むことができます。

目的は、ナップサックに詰め込んだ商品の価値の合計を最大化することです。

解法・ソースコード

以下は、PuLPを使用してこのナップサック問題を解決するコードです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from pulp import *

# ①問題を定義する
prob = LpProblem("Knapsack Problem", LpMaximize)

# ②商品の価値と重量を定義する
items = {
    "A": {"value": 10, "weight": 5},
    "B": {"value": 12, "weight": 6},
    "C": {"value": 8, "weight": 3},
    "D": {"value": 15, "weight": 7},
    "E": {"value": 4, "weight": 2}
}

# ③変数を定義する
item_vars = LpVariable.dicts("Item", items.keys(), lowBound=0, cat='Binary')

# ④目的関数を定義する
prob += lpSum([items[i]["value"] * item_vars[i] for i in items])

# ⑤制約条件を定義する
prob += lpSum([items[i]["weight"] * item_vars[i] for i in items]) <= 15

# ⑥問題を解く
prob.solve()

# ⑦結果を表示する
print("Optimal Solution: ", value(prob.objective))
for i in items:
    print(i, ": ", value(item_vars[i]))

①問題を定義する

問題を定義し、最大化問題であることを指定します。

“Knapsack Problem”は問題名であり、必須ではありませんが、問題が複雑になる場合、有用であることがあります。

②商品の価値と重量を定義する

問題に必要なデータを定義します。各商品には価値と重量があります。

この例では、5つの商品を定義しています。

③変数を定義する

商品を選択するための変数を定義します。

LpVariable.dictsを使用して、”Item”という名前の変数を作成します。

items.keys()は、変数の名前を商品名（A、B、C、D、E）に設定します。

lowBound=0は、変数が0以上であることを指定します。

cat=’Binary’は、変数がバイナリ変数であることを指定します。

これは、商品が選択されたかどうかを示すために0または1で設定されることを意味します。

④目的関数を定義する

目的関数を定義します。

この例では、商品の選択によって生じる価値の総和を最大化します。

lpSumを使用して、すべての商品の価値を変数に乗じ、それらを合計します。

⑤制約条件を定義する

制約条件を定義します。

この例では、ナップサックの容量を制限しています。

lpSumを使用して、すべての商品の重量を変数に乗じ、それらを合計し、合計が15以下であることを指定します。

⑥問題を解く

PuLPを使って問題を解きます。

⑦結果を表示する

最適解を表示します。

最適解は、value(prob.objective)を使用して得られます。

問題に使用された各変数の値を表示するために、forループが使用されています。

prob.variables()はすべての変数を返します。

各変数の名前と値を表示するには、 i.nameと i.varValueを使用します。

コードを実行すると下記のような実行結果になります。

[実行結果]
Optimal Solution:  33.0
A :  1.0
B :  0.0
C :  1.0
D :  1.0
E :  0.0

この結果から、最適な解は、商品A、商品C、および商品Dをナップサックに詰め込み、価値を合計33にすることです。

商品BとEは選択されなかったことがわかります。