积木城堡.cpp

背包类问题浅析和一些背包类问题的解答源程序。

#include <iostream>
using namespace std;

const int T = 10002, N = 109, OO = 2000000000;
int n, top=OO, a[N][N];
bool can[N][T]={0};

int main(){
    cin >>n;
    int i, j, k, s;
    for( i=1; i<=n; ++i ){
         s = j = 0;
         cin >>a[i][++j];
         while( a[i][j] != -1 ){
                s += a[i][j];
                cin >>a[i][++j];
         }
         if( s < top ) top = s;
    }
    
    for( i=1; i<=n; ++i ){
         can[i][0] = true;
         for( k=1; a[i][k]!=-1; ++k ){
              s = a[i][k];
              for( j=top; j>=s; --j )
                   can[i][j] = can[i][j] || can[i][j-s];
         }
    }
    
    for( i=top; i>=0; --i ){
         s = 1;
         for( j=n; j>0; --j )
              if( !can[j][i] ){
                  s = 0;  break;
              }
         if( s ) break;
    }
    cout <<i <<endl;

    system( "pause" );
    return 0;
}