組合せ最適化 - 典型問題 - ナップサック問題

典型問題と実行方法

ナップサック問題

容量$c(\gt 0)$のナップサックと$n$個の荷物$N=\{1,\dots,n\}$が与えられている。荷物$i \in N$の容量を$w_i(\gt 0)$、価値を$p_i(\gt 0)$とする。容量制限$c$の範囲で価値の和が最大になる荷物の詰合わせを求めよ。

実行方法

usage

Signature: knapsack(size, weight, capacity)
Docstring:
ナップサック問題
    価値の最大化
入力
    size: 荷物の大きさのリスト
    weight: 荷物の価値のリスト
    capacity: 容量
出力
    価値の総和と選択した荷物番号リスト

python

from ortoolpy import knapsack
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
print(knapsack(size, weight, capacity))

結果

(105.0, [0, 1, 3, 4, 5])

python

# pandas.DataFrame
from ortoolpy.optimization import Knapsack
Knapsack('data/knapsack.csv', 100)

	size	weight
0	21	22
1	11	12
3	9	10
4	34	35
5	25	26

データ

• data/knapsack.csv