結果

問題 No.1122 Plane Tickets
ユーザー koyumeishi
提出日時 2020-07-23 09:00:00
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,251 bytes
コンパイル時間 654 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 44,924 KB
最終ジャッジ日時 2024-06-23 17:07:58
合計ジャッジ時間 32,735 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

from __future__ import print_function
import numpy as np
from pprint import pprint

from ortools.linear_solver import pywraplp
def mip_ortools(a):
  solver = pywraplp.Solver('mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
  infinity = solver.infinity()
  x = [solver.IntVar(0.0, infinity, f'x_{i}') for i in range(5)]

  for i in range(5):
    solver.Add(sum(x[(i+j)%5] for j in range(3)) <= a[i])

  solver.Maximize(sum(x))
  status = solver.Solve()
  if status == pywraplp.Solver.OPTIMAL:
    print('OPTIMAL')
    print('Solution:')
    print('Objective value =', solver.Objective().Value())
    for i in range(5):
      print(f'x_{i} =', x[i].solution_value())
  else:
      print('The problem does not have an optimal solution.')
  print(list(map(lambda w: w.solution_value(), x)))
  return int(solver.Objective().Value())

import pulp
import sys
def mip_pulp(a):
  problem = pulp.LpProblem("prob", pulp.LpMaximize)
  x = [pulp.LpVariable(f'x_{i}', 0, sys.maxsize, pulp.LpInteger) for i in range(5)]
  problem += (sum(x), "Objective")
  for i in range(5):
    problem += (sum(x[(i+j)%5] for j in range(3)) <= a[i], f'Constraint_{i}')
  print(problem)
  res = problem.solve()
  print(f"Status = {pulp.LpStatus[res]}")
  print(f"Objective = {pulp.value(problem.objective)}")
  for i in range(5):
    print(f'x_{i} = {pulp.value(x[i])}')
  return pulp.value(problem.objective)


from scipy.optimize import linprog
def lp(a):
  c = np.ones(5)
  A = np.array([[1 if (j-i+5)%5 <= 2 else 0 for j in range(5)] for i in range(5)])
  b = np.array(a)
  pprint(c)
  print(A)
  pprint(b)
  res = linprog(-c, A, b)
  print(res)
  return int(-res.fun + 0.001)

if __name__ == '__main__':
  # input:
  # 1048577 1048579 1048576 1048577 1048577
  a = list(map(int, input().split()))
  while True:
    # a = np.random.randint(0, 4, 5) + 2**20
    ans_mip_ortools = mip_ortools(a)
    ans_mip_pulp = mip_pulp(a)
    ans_lp = lp(a)

    eps = 1e-1
    if np.abs(ans_mip_ortools - ans_lp) > eps or np.abs(ans_mip_pulp - ans_lp) > eps:
      print("MIP != LP")
      pprint(ans_mip_ortools) # 1747627
      pprint(ans_mip_pulp)    # 1747628
      pprint(ans_lp)          # 1747628
      pprint(a)
      exit()
    # else:
      # print("OK")
    break
0