Codeforces 3B

想定解なんて知ってるわけないじゃん...。

問題

大きさ1のものと2のものしかないナップザック問題。

解答例

大きさごとに分けて、価値の大きい順にソートしておく。詰められる量が奇数なら、大きさ1の側から一番価値の大きいものを1個詰めておく。後は、大きさ1のもの二個と、大きさ1のもの一個で、価値の大きい側を順番に詰めていくだけ。最後に大きさ1のものが一個しかない状態が発生し得るので、それについても適宜対応する必要がある。