0-1ナップザック問題解いた

この記事は PMOB Advent Calendar 2015 の 15 日目の記事です．

この前授業の課題で0-1ナップザック問題をソルバで解いてねって感じの問題が出たのでサッと書きました。

pythonにpulpとかいうglpk使って解けるモジュール？(よくわからない)あったので、それを使ったらあっさりでした。
以下コード

#! /usr/bin/python
# encoding: utf-8

import pulp

# コンストラクタ
prob = pulp.LpProblem('knapsack', pulp.LpMaximize)

# 詰める荷物の数
print('num of obj: ', end='')
n = int(input())

a = [pulp.LpVariable('baggage{0}'.format(
    i), cat=pulp.LpBinary) for i in range(n)]
v = []
s = []
for i in range(n):
    print('[{0}]'.format(i))
    # 荷物の価値
    print('value: ', end='')
    v.append(int(input()))
    # 荷物のサイズ
    print('size: ', end='')
    s.append(int(input()))

# ナップザックの容量
print('knapsack capasity: ', end='')
b = int(input())

# 目的関数
prob += pulp.lpDot(v, a)
# 制約条件
prob += pulp.lpDot(s, a) <= b

# 問題も表示しておく
print()
print(prob)
prob.solve()

# 結果
print("Result:")
for i in range(n):
    print(a[i].getName(), int(a[i].value()))

lpDotとかいうリストの内積求めてくれる奴がめっちゃ便利でした。
ていうかソルバ神か