割り算を避ける(doubleを避ける)

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_B

解法など

  • http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3586431
  • 貪欲に「重さ当たりの価値」が高いものから取っていけばいい
  • 「重さ当たりの価値」を求めるには v / w 割り算が発生し、結果をdoubleに入れることになる
  • しかし、やりたいことは、それの比較
    • v0 / w0 と v1 / w1 の比較
  • これは分母を払ってv0 * w1 と v1 * w0 で比較しても大小が求められ、整数のみでできる
  • こちらの方が誤差を気にしなくて済む