PuLP를 사용하여 ABC 219D 문제 해결(정수 계획 문제)

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