3回目は整数計画問題ということでナップサック問題を扱います。Knapsack ProblemちぢめてKPというのがツウです。ナップ「ザ」ックと言わないのもツウです。

ナップサック問題

コソドロのあなたは、お店で盗難を計画しています（なんと物騒な）。

闇市場での売値が $v_i$ ，重量 $w_i$ (kg)の品物を何個かずつ持って、C(kg)までなら持って逃げられそうです。何を何個ずつ盗むのがよいでしょうか。（制限に収まる限りは何個でも持ってよいのが整数KPです。）

（ちなみに、品物がどれも1点モノで、持ち出すとしても1個ずつの場合が0-1KPです。0-1KPのほうがお好きな方にはすみませんが、今回は整数計画の例題として整数KPを雑に定式化して雑に解きます。）

ナップサック問題の定式化

品物の集合を大文字の $I$ ，品物iを盗む個数を $x_i (i \in I)$ とすると、KPは以下の最大化問題になります。

$\begin{aligned} \text{maximize}\quad & \sum _ {i \in I} v _ i x _ i \\ \text{subject to}\quad & \sum _ {i \in I} w_ i x _ i \le C \\ & x _ i \in \mathbb{N} _ {0} \end{aligned}$

※ $\mathbb{N} _ {0}$ は0を含む自然数（つまり非負整数）です。

これだけですからPuLPでの定式化も簡単です。

import pulp
from math import floor

# data
value = [1,3,2,1,3,4]
weight = [2,3,4,1,4,3]
itemsize = 6

capacity = 10

# モデルオブジェクト
model = pulp.LpProblem("IntKP", pulp.LpMaximize)

# 変数オブジェクト
x = [
     pulp.LpVariable("item{}".format(i), lowBound=0, upBound=floor(capacity/weight[i]), cat=pulp.LpInteger)
     for i in range(itemsize)
    ]

LpVariableの引数で cat=pulp.LpInteger とすると整数変数に指定できます。

cat=pulp.LpBinaryで0-1変数を指定できます。そうすると0-1KPになります。書き換えて試してみてください。

ここでも，輸送問題のときと同様，自明な上界 $\lfloor C/w_i \rfloor$ があるので一応指定してあげます。（i番目の品物だけを詰めることを考えると，キャパシティを超えない上限個数がある）

# 目的関数
model += pulp.lpSum([value[i] * x[i] for i in range(itemsize)]), "Objective"

# 制約条件
# ナップサックの重量制限
weightsum = pulp.lpSum([weight[i] * x[i] for i in range(itemsize)])
model += weightsum <= capacity, "Capacity"

# 求解
model.solve()

print("Optimal Value =", pulp.value(model.objective))
for i, xi in enumerate(x):
    print("Item{} (V={} W={})".format(i, value[i], weight[i]), pulp.value(xi))
print("Knapsack holds {} kg".format(pulp.value(weightsum)))

Optimal Value = 13.0
Item0 (V=1 W=2) 0.0
Item1 (V=3 W=3) 0.0
Item2 (V=2 W=4) 0.0
Item3 (V=1 W=1) 1.0
Item4 (V=3 W=4) 0.0
Item5 (V=4 W=3) 3.0
Knapsack holds 10.0 kg