TopCoder SRM 598, Divisin 1, Level 1 : BinPacking

概要

N 個の品物があり、i 番の品物の重さは item[ i ] である。
また、全ての品物の重さは 100 以上 300 以下である。
これらの品物をキャパシティ 300 の箱に入れる。
最小でいくつの箱があれば全ての品物を箱に入れることができるか求めよ。

解法

制約より、重さ 100 の品物を 3 つまとめたときだけ、一つの箱に 3 個の品物を入れることができます。
それ以外のとき、一つの箱に入る品物の数は高々 2 個です。

3 つまとめる場合を除外して考えます。
このとき、ある品物を空の箱に入れた後、更にもう一つの品物を入れられるとすれば、そのうち最も重いものを入れた方が得になります。
（ 3 個以上の品物を入れることはないので、残り容量の効率的な使い方などは考えなくてよい）

こう書くと 3 つ入れる箱をいくつにするか全部試すのが正攻法っぽいですが、以下の Greedy アルゴリズムで解けます。

• 重さの降順で品物を走査し、追加できる箱があればそこに追加する
• そのような箱が存在しないとき、箱を増やしてそこに入れる

空き容量 100 の箱 3 つに対し、重さ 100 を 3 つ入れた箱から分配する操作は得ですが、逆は無いのでこれでよくなります多分。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

const int CAPACITY = 300;

class BinPacking
{
public:
	int N;
	int total;

	int minBins( vector <int> item )
	{
		this -> N = item.size();
		this -> total = accumulate( ALL( item ), 0 );

		sort( ALL( item ), greater<int>() );

		VI bins( N, 0 );
		REP( i, 0, N )
		{
			REP( j, 0, N )
			{
				if ( bins[j] + item[i] <= CAPACITY )
				{
					bins[j] += item[i];
					break;
				}
			}
		}

		return N - count( ALL( bins ), 0 );
	}
};