首页 > 代码库 > zoj 1880 - Tug of War
zoj 1880 - Tug of War
题目:有n个人分成两组,两组人数差不能超过1,找到两组的人重量之差的最小值。
分析:dp,二维01背包。
由于必须放在两个组中的一组,直接背包全部可到状态,
取出相差不超过 1的最接近 sum/2的值就可以。
说明:430ms。
。好慢啊。。
(2011-9-30 18:37)。
#include <stdio.h> #include <stdlib.h> #include <string.h> int f[ 52 ][ 22501 ]; int h[ 101 ]; int main() { int n,sum; while ( scanf("%d",&n) != EOF && n != -1 ) { sum = 0; for ( int i = 1 ; i <= n ; ++ i ) { scanf("%d",&h[ i ]); sum += h[ i ]; } memset( f, 0, sizeof( f ) ); f[ 0 ][ 0 ] = 1; for ( int i = 1 ; i <= n ; ++ i ) for ( int l = n/2+1 ; l > 0 ; -- l ) for ( int j = sum/2 ; j >= h[ i ] ; -- j ) if ( f[ l-1 ][ j-h[ i ] ] ) f[ l ][ j ] = 1; int move = sum/2; while ( move ) { if ( n%2 == 0 && f[ n/2+0 ][ move ] ) break; if ( n%2 == 1 && f[ n/2+1 ][ move ] ) break; if ( n%2 == 1 && f[ n/2-0 ][ move ] ) break; -- move; } printf("%d %d\n",move,sum-move); } return 0; }
zoj 1880 - Tug of War
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。