Hatena::Grouptopcoder

hasiの日記

 | 

2010-05-09

Marathon Match 59 - BookSelection

06:04

今更だけど。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14227&pm=10885

本棚に本を詰め込む。本にはそれぞれ価値があって、価値の合計が得点になる。本と本棚には幅と高さがあって、リンク先の図のように詰め込まないといけない。制限時間2秒。なんか短い。

手法

DPとか貪欲とか使って適当に詰めた。

DP

ナップサック問題のDP。一段に入れられる最適解を計算。

貪欲法

整数計画なのを線形計画にすると貪欲法で最適な値が得られるはず。たぶんDP<=貪欲法になるのでこれで枝刈りできる。

手順

大雑把に。

  1. 価値の合計/(段の高さ+10)が最大になるような段の高さを求めて本を詰める
  2. 本が入らなくなるまで1.を繰り返す
  3. 1.と2.で求めた段の高さを元に、高さの小さい段から本を詰め直す
  4. 適当にそれぞれの段の高さを決めて、高さの小さい段から本を詰めて、結果が良くなったら更新
  5. TLEしない程度に4.を繰り返す

結果

53位。Rating: 1763 → 1769

 |