程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 多重背包

多重背包

編輯：C++入門知識

學習了二進制優化，吼吼，多重背包是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;
}