2016年01月24日
python備忘録12（ナップサック問題）
皆さんは
ナップサック問題というのを
ご存知でしょうか？
私は、去年ころ、
pythonの勉強会に参加した際に
知りました＾＾
ナップサック問題というのは、
「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」 by wiki
です。
とっくに忘れていたのですが、
職場の仲間が、
「こんなにたくさんのファイルをメールで送らなきゃいけないんだけど、
相手のメールサーバーが一度に5MBまでしか受け取れないんだ。
できるだけメールの数を少なくしたいんだけど…」
とぼやいたのが
きっかけで、
頭の片隅にあったこのナップサック問題を
思い出したのが今回の始まりでした。
pythonのpulpというライブラリをインストールしてインポートすることで、
あっという間に解けてしまうのですが、
自分でアルゴリズムをつくるとなると
かなり難しいです。
pulpを使用した例としては、
＃10個ある45〜3200KBまでのファイル
と、上記6個のファイルを選ぶのが最適と
教えてくれます。
世の中は便利になったなり…。
wikiより
ナップサック問題というのを
ご存知でしょうか？
私は、去年ころ、
pythonの勉強会に参加した際に
知りました＾＾
ナップサック問題というのは、
「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」 by wiki
です。
とっくに忘れていたのですが、
職場の仲間が、
「こんなにたくさんのファイルをメールで送らなきゃいけないんだけど、
相手のメールサーバーが一度に5MBまでしか受け取れないんだ。
できるだけメールの数を少なくしたいんだけど…」
とぼやいたのが
きっかけで、
頭の片隅にあったこのナップサック問題を
思い出したのが今回の始まりでした。
pythonのpulpというライブラリをインストールしてインポートすることで、
あっという間に解けてしまうのですが、
自分でアルゴリズムをつくるとなると
かなり難しいです。
pulpを使用した例としては、
＃10個ある45〜3200KBまでのファイル
s=[45,160,700,1500,3200,2100,489,499,800,430]
# その中から５MB（5000KB）に収まるグループを選ぶべく最大収量を指定する
c=5000
# pulpライブラリをインポートする
from pulp import *
# ｓに収容したファイルが何個あるか計数し、後述の繰り返しのためのrangeにrnとしてその数を収容する。
rn = range(len(s))
# モデル準備
m = LpProblem('knapsack', LpMaximize)
# 変数(i番目のファイルをいれるかどうかの0/1)
v = [LpVariable('v%d' % i, cat = LpBinary) for i in rn]
# 目的関数
m += lpDot(s, v)
# 制約
m += lpDot(s, v) <= C
# 解く
m.solve()
# 出力
print(LpStatus[m.status], sum(s[i] * value(v[i]) for i in rn))
print([s[i] for i in rn if value(v[i]) > 0.5])
('Optimal', 4994.0)
[45, 160, 700, 1500, 2100, 489]
と、上記6個のファイルを選ぶのが最適と
教えてくれます。
世の中は便利になったなり…。
wikiより
【このカテゴリーの最新記事】
-
no image
-
no image
-
no image
-
no image
-
no image
-
-
no image
-
-
no image
-
no image
