学习了二进制优化 多重背包
学习了二进制优化，吼吼，多重背包是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
[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 ;
}
&nbs
补充：软件开发 , C++ ,
