POJ 2782 Bin Packing

問題

アイテムがN個あり、それぞれの重さが与えられる。これらのアイテムをビンに詰めたいとする。一つのビンにたいして最大で2個までのアイテムを詰められる。このとき必要な最小のビンの数を求めよ。ただし一つのビンに詰めるアイテムの重さの和がLより大きくなってはいけない。

やりかた

ビンパッキング問題なので普通なら効率的にはできないが、ビンに入れられるアイテム数がせいぜい2なので貪欲で解ける。最小の重みのアイテムと、合わせてビンに詰めることができる最大の重みを持つアイテムを見つけてこれら2つを消去し、ビン1つにカウントする。合わせて詰められるアイテムが見つからない場合は単独で消去し、ビン1つにカウントする。これをアイテムがなくなるまで繰り返せばいい。アイテムはmultisetで管理し、条件に合う最大重みのアイテムを見つける処理はlower_boundで二分探索する。

以下ソース。

#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#define ALL(c) (c).begin(), (c).end()

using namespace std;

int main(){
  int N, L;
  scanf("%d %d", &N, &L);

  multiset<int> x;
  for(int i = 0; i < N; i++){
    int a;
    scanf("%d", &a);
    x.insert(a);
  }

  int ans = 0;
  while(!x.empty()){
    int b = L - *x.begin();//計算上詰められる最大重み
    multiset<int>::iterator it = x.begin();
    it =  x.upper_bound(b);
    if(it != x.begin()) it--;
    
    if(it != x.begin()) x.erase(it); //抱き合わせできるものが見つかった場合は消す
    x.erase(x.begin());//今見ているアイテムを消す
    ans++;
  }

  printf("%d\n", ans);
  return 0;
}