TopCoder SRM 598 Div1 Easy BinPacking

問題

容量300の袋にn個の物体をつめる。
i番目の物体の大きさはitem[i]である。一つの袋には大きさの和が300以下になるように好きに物体を詰められる。
全ての物体を詰めるのに必要な袋の枚数の最小値を求めよ。

制約条件

n≦50
100≦item[i]≦300

方針

大きさ100のビンを除けば、全てのビンは高々2つしか同時に袋に入らない。
ので貪欲に大きい順にペアにするだけ。
あまった100は3つずつペアにすればよい。

ソースコード

class BinPacking {
	public:
	int minBins(vector <int> item) {
		int ans = 0;
		int n = item.size();
		sort(all(item));
		
		for(int i = n - 1; i >= 0; i--) if(item[i] > 100 && item[i] < inf){
			for(int j = i - 1; j >= 0; j--) if(item[i] + item[j] <= 300){
				item[j] = inf;
				ans++;
				goto END;
			}
			ans++;
			END:;
		}
		int cnt = 0;
		rep(i, n) if(item[i] == 100) cnt++;
		
		return ans + (cnt + 2) / 3;
	}
};