読者です 読者をやめる 読者になる 読者になる

SRM 598 Div2 Medium BinPackingEasy

問題

SRM 598 - TopCoder Wiki

容量が101から300の商品が与えられた時,これらの商品を複数の容量300の瓶に詰め込むことを考える. 全て詰め込むのに必要な最小に瓶の数を答える問題

解答

入力の商品の容量が101から300というのがポイント. つまり最適に詰め込めたとしても,各瓶には最大で2つの商品しかつめ込むことが出来ない. とすると大きな商品と小さな商品で順番に同じ瓶に詰め込んでいくことで最適解を求めることが出来る.

class BinPackingEasy
{
public:
  int minBins(vector <int> item)
    {
      int n = item.size();
      sort(item.begin(), item.end());
      int res = 0;
      for(int i = 0, j = n-1; i <= j;){
        if (item[i] + item[j] <= 300){
          i++;
          j--;
          res++;
        }else{
          j--;
          res++;
        }
      }
      return res;
    }
};