SRM415

TopCoder

250

重い荷物から順にクレーンに割り当てるというのを繰り返せばよい

500

n( <= 32)個のものの値段と価値が与えられたときに総価値をK以上にするために必要となる最小の値段を求めよという問題。式で書くと
\min \sum_{s \in S} p_s \\ s.t \sum_{s \in S} v_s >= K
なるSを求めよという問題になり、これは
\max \sum_{s \not \in S} p_s \\ s.t \sum_{s \not \in S} v_s <= \sum_{s \in (1..n)} v_s - K
になるため、ナップザック問題と等価になる。だから全探索するしかないんだが適当な枝刈りをしただけでは間に合わなくて、n個の集合を半分ずつに分けて探索する必要がある。