はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける線形計画問題・整数計画問題まとめ

線形計画問題

  • LP : Linear Programming
  • シンプレックス法という解法があるが、これを使うのはまれ
  • 双体というのを取ると、フロー問題に帰着できる場合がある 参考1 参考2

整数計画問題

  • IP : Integer Programming
  • これを解くのは難しい
  • 枝刈りを上手くやる全探索や動的計画法で解く