http://wikioi.com/problem/2144/
// File Name: wiki2144.cpp // Author: bo_jwolf // Created Time: 2013年08月17日 星期六 15时00分04秒 #include<vector> #include<list> #include<map> #include<set> #include<deque> #include<stack> #include<bitset> #include<algorithm> #include<functional> #include<numeric> #include<utility> #include<sstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<ctime> using namespace std; int main() { int n , t , m = 100 , p , a[ 16 ] , b[ 16 ] , c[ hash ] , d[ hash ]; for(int i=1;i<=hash;i++) { c[ i - 1 ] = -1 ; d[ i - 1 ] = 100; } scanf( "%d%d" , &n , &m ) ; t = n / 2 ; n -= t ; for( int i = 1 ; i <= n ; i++ ) scanf( "%d" , &a[ i ] ); for( int i = 1 ; i <= t ; i++ ) scanf( "%d" , &b[ i ] ) ; for( int i = 0 ; i < 1 << n ; i++ ) { int z = 0 , w = m ; for( int j = 1 ; j <= n ; j++ ) if( i & ( 1 << j - 1 ) ) { w -= a[ j ] ; z++ ; } if( w < 0 ) continue; else p = w % hash ; while( c[ p ] >= 0 && c[ p ] != w ) p = ( p + 1 ) % hash; c[ p ] = w; d[ p ] = min( d[ p ] , z ); } for( int i = 0 ; i < 1 << t ; i++ ) { int z = 0 , w = 0 ; for( int j = 1 ; j <= n ; j++ ) { if( i & ( 1 << j - 1 ) ) { w += b[ j ] ; z++ ; } } if( w > m ) { continue; } else { p = w % hash ; } while( c[ p ] >= 0 && c[ p ] != w) { p = ( p + 1 ) % hash ; } if( c[ p ] >= 0 ) { m = min( m , z + d[ p ] ) ; } } printf( "%d" , m ) ; return 0; }