No Caffeine, No Life

プログラミング(主にPython)

Aizu Online Judge: 割り当て (探索の応用:最適解の計算)

探索の応用:最適解の計算

気づかないといけないことは、

  • 各トラックは、与えられた荷物をその順番通りにしか積めない
  • 求める最大貨物量の最小値は、与えられた荷物リストのなかの最大値以上、その総和以下になる

次にすることは、

  • 求める最小値は、区間(荷物リストの最大値、荷物リストの総和)の範囲内で、バイナリーサーチで求める。
  • 与えられた台数の各トラックの積み荷量が条件を満たしていればOK.満たしていなければ、範囲を変更して探索する。

そうしてコードを書いていくと、例えば次のようになる:

広告を非表示にする