yukicoder : No.50 おもちゃ箱

さっきの42に比べるとだいぶ気楽。
http://yukicoder.me/problems/81

問題

N個のおもちゃとM個の箱がある。
またそれぞれの体積が与えられる。

箱の中には、その体積以下であればおもちゃを複数入れることができる。
全おもちゃをいずれかの箱に入れるには最小で何個の箱があればよいか。

解法

当然箱は大きい順に使っていく。
bitdpの要領で、まだ箱に入っていないおもちゃのうち、組み合わせて箱に収まる組み合わせを入れていけば良い。

int N,M;
int A[21],B[21];
int MA[1<<11];
int dp[12][1<<10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cin>>M;
	FOR(i,M) cin>>B[i];
	
	FOR(i,1<<N) FOR(j,N) if(i&(1<<j)) MA[i]+=A[j];
	sort(B,B+M);
	reverse(B,B+M);
	dp[0][0]=1;
	FOR(i,M) {
		int mask,mask2;
		FOR(mask,1<<N) FOR(mask2,1<<N) if((mask&mask2)==0 && dp[i][mask] && MA[mask2]<=B[i]) dp[i+1][mask|mask2]=1;
		
		if(dp[i+1][(1<<N)-1]) return _P("%d\n",i+1);
	}
	_P("-1\n");
}

まとめ

このころってまだ参加者数名だったんだね。