Codeforces 3B
想定解なんて知ってるわけないじゃん...。
問題
大きさ1のものと2のものしかないナップザック問題。
解答例
大きさごとに分けて、価値の大きい順にソートしておく。詰められる量が奇数なら、大きさ1の側から一番価値の大きいものを1個詰めておく。後は、大きさ1のもの二個と、大きさ1のもの一個で、価値の大きい側を順番に詰めていくだけ。最後に大きさ1のものが一個しかない状態が発生し得るので、それについても適宜対応する必要がある。
想定解なんて知ってるわけないじゃん...。
大きさ1のものと2のものしかないナップザック問題。
大きさごとに分けて、価値の大きい順にソートしておく。詰められる量が奇数なら、大きさ1の側から一番価値の大きいものを1個詰めておく。後は、大きさ1のもの二個と、大きさ1のもの一個で、価値の大きい側を順番に詰めていくだけ。最後に大きさ1のものが一個しかない状態が発生し得るので、それについても適宜対応する必要がある。