学习了二进制优化，吼吼，多重背包是01和完全背包的结合
我的代码:
HDU1059 Dividing
[cpp]
#include
#include
#include
using namespace std;?
#define N 60006?
#define max(a,b) a > b ? a : b?
int V,num[7],dp[N];?
void OneZeroPack(int c){???????????????????????????????? //01背包?
????? for( int i = V ; i >= c ; i-- ){?
??????????? dp[i] = max( dp[i] , dp[i-c] + c );?
????? }?
}?
void CompletePack(int c){?????????????????????????????? //完全背包?
????? for( int i = c ; i <= V ; i++ )?
??????????? dp[i] = max( dp[i] , dp[i-c] + c) ;?
}?
void MultiplePack(){?????????????????????????????????????? //多重背包?
?????? for( int i = 1 ; i <= 6 ; i++ ){?
??????????? if( i * num[i] >= V )?
????????????????? CompletePack(i) ;?
??????????? else{?
????????????????? int k=1;?
????????????????? while( k < num[i] ){???????????????? //二进制优化?
??????????????????????? OneZeroPack( i*k ) ;?
??????????????????????? num[i] -= k;?
??????????????????????? k <<= 1;?
????????????????? }?
????????????????? OneZeroPack( num[i]*i ) ;?
??????????? }?
????? }?
}?
int main()?? {?
????? int count=0;?
????? while(1)????? {?
??????????? count++ ;?
??????????? int sum=0;?
??????????? memset( num , 0 ,sizeof(num) );?
??????????? memset( dp , 0 ,sizeof(dp) );?
??????????? for( int i = 1 ; i <= 6 ; i++ ){?
????????????????? scanf( "%d" , &num[i] );?
????????????????? sum += ( num[i] * i) ;?
??????????? }?
??????????? if( !sum )?
????????????????? break ;?
??????????? printf( "Collection #%d:\n" ,count ) ;?
??????????? if( sum&1 )?
????????????????? printf( "Can't be divided.\n\n" ) ;?
??????????? else?
??????????? {?
????????????????? V = sum/2;?
????????????????? MultiplePack();?
????????????????? if( dp[V] == V )?
??????????????????????? printf( "Can be divided.\n\n" ) ;?
????????????????? else?
??????????????????????? printf( "Can't be divided.\n\n" ) ;?
??????????? }?
????? }?
????? return 0;?
}?
HDU 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
[cpp]?
#include
#include
#include
#include
#include
#include
#include
//#define LOCAL?
#define N 105?
using namespace std;?
int dp[N];?
void OneZeroPack( int v , int n , int w ){?
????? for( int i = v ; i >= n ; i-- )?
??????????? dp[i] = max( dp[i] , dp[i-n] +w ) ;?
}?
void CompletePack( int v , int n , int w ){?
????? for( int i = n ; i <= v ; i++ )?
??????????? dp[i] = max( dp[i] , dp[i-n] +w ) ;?
}?
void MultipliePack( int v , int c, int w , int n){?
????? if( n*c >= v ){?
??????????? CompletePack( v , c , w ) ;?
??????????? return ;?
????? }?
????? int k = 1 ;?
????? while( k < n ){?
??????????? OneZeroPack( v , k*c , k*w ) ;?
??????????? n -= k ;?
??????????? k <<= 1 ;?
????? }?
????? OneZeroPack( v , n*c , n*w ) ;?
}?
int main() {?
? www.2cto.com
?? #ifdef LOCAL?
????? freopen("Input.txt","r",stdin);?
????? freopen("Output.txt","w",stdout);?
?? #endif?
????? int C , n , m , p , h , c , i ;?
????? scanf( "%d" , &C ) ;?
????? while( C-- ){?
??????????? memset( dp , 0 , sizeof( dp ) ) ;?
??????????? scanf( "%d%d" , &n , &m ) ;?
??????????? for( i = 1 ; i <= m ; i++ ){?
????????????????? scanf( "%d%d%d" , &p , &h , &c ) ; //价?? 重? 袋数?
????????????????? MultipliePack( n , p , h , c ) ;?
??????????? }?
??????????? printf( "%d\n" , dp[n] );?
????? }?
?
????? return 0;?
}?
?作者：ice2013