AtCoder ABC 338 C - Leftover Recipesを整数計画問題として解く

整数計画問題であることが自明です。料理Aを$x$人分, 料理Bを$y$人分作る時に$x+y$を最大化したいです。

maximize: $z = x + y$
subject to:$x \cdot a[i] + y \cdot b[i] \leq q[i]$

を解けば良いです。

ortools

ortools

n = int(input())
q = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

from ortools.sat.python import cp_model
import sys
model = cp_model.CpModel()

ub = 10**6 + 10
x = model.NewIntVar(0, ub, 'x')
y = model.NewIntVar(0, ub, 'y')

for i in range(n):
    model.Add(a[i] * x + b[i] * y <= q[i])

model.Maximize(x + y)
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print(int(solver.ObjectiveValue()))
    print("x, y = ",solver.Value(x),solver.Value(y), file = sys.stderr)
else:
  assert False