URBAN HACKSの広告(試験時間90分)のPuLPを使った解法

きっかけ

通勤の電車の中で次のような広告を見かけました。
(またかよ！）

限られた試験時間90分の中で、どの問題に取り組めば効率的よく最も高い点を撮れるか。
問題1 6点 所要時間12分
問題2 11点 所要時間26分
以下略

ようするに、問題を解くのに必ず所要時間がかかって部分点は存在しないという条件です。

前回は10パズルでしたが、今回は見た瞬間にpulpかよと思いました。
しかも、一時期話題になったマクドナルド（だっけ？）メニュー最適化問題。

こういうの、いわゆるナップサック問題というらしいです。
しかも、マクドナルドのメニューよりずいぶん簡単です。

これ、言っちゃあ悪いけど出題者が応募者を測っているつもりで、出題者の程度が見極められてますよっと。

文句言っててもしょうがないので、ちゃちゃっとコード書きます。
手抜きモードなので所要時間と点数で配列分けたのはすんまそん。
結果が1.0のの問題を解くのが解となります。

解法(コード)

import pulp
import sys

limit_time = 90  # 問題の制限時間
points  = [ 6, 11, 20, 12, 10, 19, 14, 8]  # 問題の点数
minutes = [12, 26, 48, 28, 25, 45, 31, 15]  # 問題の所要時間

if len(points) != len(minutes):
    print("問題設定ミスってまっせ！")
    sys.exit(1)

# 問題を定義。pulp.LpMaximizeで点数が最大になる条件を指定
prob = pulp.LpProblem('examination', sense=pulp.LpMaximize)

# 変数の定義。問題を解くかどうかを0,1で示す
vars = [pulp.LpVariable('{}'.format(x), cat='Binary', lowBound=0, upBound=1) for x in range(len(points))]
prob += pulp.lpDot(points, vars)  # values(係数),vars(変数)の内積を目的関数として登録
prob += pulp.lpDot(minutes, vars) <= limit_time  # 試験の制限時間を制約条件として追加

# 実行
status = prob.solve()

#結果表示
print([x.value() for x in vars])