結果

問題 No.1122 Plane Tickets
ユーザー koyumeishikoyumeishi
提出日時 2020-07-23 09:00:00
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 2,251 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 10,976 KB
実行使用メモリ 30,032 KB
最終ジャッジ日時 2023-09-05 21:48:23
合計ジャッジ時間 11,437 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
権限があれば一括ダウンロードができます

ソースコード

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