多重背包

学习了二进制优化，吼吼，多重背包是01和完全背包的结合

我的代码:

HDU1059 Dividing
[cpp]
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
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 <cmath> 
#include <cstdio> 
#include <string> 
#include <cstdlib> 
#include <cstring> 
#include <iostream> 
#include <algorithm> 
//#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