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; } };