//MiYu原创, 转帖请注明 : 转载自 #include < iostream > using namespace std; int V[ 51 ]; int M[ 51 ]; int bst[ 125005 ]; int main (){ int N; while ( scanf ( " %d " , & N ), N > 0 ) { int sum = 0 ; for ( int i = 1 ; i <= N; ++ i ) { scanf ( " %d%d " , & V[i], & M[i] ); sum += V[i] * M[i]; } int total = sum; sum /= 2 ; memset ( bst, 0 , sizeof ( bst ) ); for ( int i = 1 ; i <= N; ++ i ) { for ( int j = 1 ; j <= M[i]; ++ j ) { for ( int k = sum; k >= V[i] ; k -= V[i] ) { if ( bst[ k - V[i] ] + V[i] > bst[k] ) { bst[k] = bst[ k - V[i] ] + V[i] ; } } } } int other = total - bst[sum]; if ( other > bst[sum] ) { swap ( other, bst[sum] ); } printf ( " %d %d\n " , bst[sum], other ); } return 0 ; }
下面的是奋斗哥的代码 ,: // Author: Tanky Woo // HDOJ 1171 #include < iostream > using namespace std; int c1[ 250010 ], c2[ 250010 ]; int value[ 55 ]; int amount[ 55 ]; int main(){ int nNum; while (scanf( " %d " , & nNum) && nNum > 0 ) { memset(value, 0 , sizeof (value)); memset(amount, 0 , sizeof (amount)); int sum = 0 ; for ( int i = 1 ; i <= nNum; ++ i) { scanf( " %d %d " , & value[i], & amount[i]); sum += value[i] * amount[i]; } memset(c1, 0 , sum * sizeof (c1[ 0 ])); memset(c2, 0 , sum * sizeof (c2[ 0 ])); for ( int i = 0 ; i <= value[ 1 ] * amount[ 1 ]; i += value[ 1 ]) c1[i] = 1 ; int len = value[ 1 ] * amount[ 1 ]; for ( int i = 2 ; i <= nNum; ++ i) { for ( int j = 0 ; j <= len; ++ j) for ( int k = 0 ; k <= value[i] * amount[i]; k += value[i]) { c2[k + j] += c1[j]; } len += value[i] * amount[i]; for ( int j = 0 ; j <= len; ++ j) { c1[j] = c2[j]; c2[j] = 0 ; } } for ( int i = sum / 2 ; i >= 0 ; -- i) if (c1[i] != 0 ) { printf( " %d %d\n " , sum - i, i); break ; } } return 0 ;}