ABC219D問題をPuLPを用いて解く（整数計画問題）

問題はこちら
D - Strange Lunchbox
解説はこちら
D - Strange Lunchbox　解説

ナップザック問題と同じ匂いがすると思う．解説でもDPが出てくる．最近，Pythonではじめる数理最適化という以下の本を読んだので，PuLPを使って解いてみようと思い，この記事を書いています．
https://www.amazon.co.jp/dp/B09G9VZ4PH/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1

PuLPを使うと以下のようになると思う．

main.py

from pulp import *


def solve(N, X, Y, takoyaki, taiyaki):
    cand = [LpVariable('x%d' % i, cat=LpBinary) for i in range(N)]  # 整数計画問題として捉える 　LpBinary 0 or 1
    prob = LpProblem('D_Strange_Lunchbox', sense=LpMinimize)
    prob += lpSum(cand)  # 目的関数の設定
    prob += lpDot(takoyaki, cand) >= X  # 制約追加（たこ焼きの個数）
    prob += lpDot(taiyaki, cand) >= Y  # 制約追加（たい焼きの個数）

    status = prob.solve()

    if status == -1:
        print("Impossible...")
    else:
        res = int(sum(cand[i].value() for i in range(N)))

        print(f"{res}個買えばいいよ！")

        total_x, total_y = 0, 0
        for i in range(N):
            if int(cand[i].value()) == 1:
                print(f"{i+1}番目を買ってね")
                total_x += takoyaki[i]
                total_y += taiyaki[i]
        print(f"Total takoyaki:{total_x}, Total taiyaki:{total_y}")


if __name__ == "__main__":
    N = int(input())
    X, Y = map(int, input().split())

    takoyaki = []
    taiyaki = []
    for i in range(N):
        n1, n2 = map(int, input().split())
        takoyaki.append(n1)
        taiyaki.append(n2)

    solve(N, X, Y, takoyaki, taiyaki)

入力データは以下のコードで作成．

import numpy as np

with open('input.txt', mode='w') as f:
    f.write("100\n")
    f.write("1000 1000\n")
    for i in range(100):
        x, y = np.random.randint(100), np.random.randint(100)
        f.write(f"{x} {y}\n")

以下のコマンドで実行

python main.py < input.txt

結果

もっといい書き方あったら教えてください！！