科技庄园ac.cpp

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

#include <iostream>
using namespace std;

const int N = 109;
int n, m, t, a, b[N][N], c[N][N];
void Input( void );                       // n, m, t, a, b[], c[]

const int TN = N * N;
int tw, tn, w[TN], v[TN], tot[TN], f[N]={0};
void InitBag( void );
int Dp( void );

int main(){
    Input();
    InitBag();
    cout <<Dp() <<endl;
    system( "pause" );
    return 0;
}

void Input( void ){
     cin >>n >>m >>t >>a;
     int i, j;
     for( i=1; i<=n; ++i )
     for( j=1; j<=m; ++j )
          cin >>b[i][j];
     for( i=1; i<=n; ++i )
     for( j=1; j<=m; ++j )
          cin >>c[i][j];
     return;
}

void InitBag( void ){
     tw = t;
     if( tw > a-1 ) tw = a-1;
     
     tn = 0;
     int i, j;
     for( i=1; i<=n; ++i )
     for( j=1; j<=m; ++j )
     if( (b[i][j]>0) && (c[i][j]>0) ){
          ++tn;
          w[tn] = i + i + j + j;
          v[tn] = b[i][j];
          tot[tn] = c[i][j];
     }
     return;
}

int Dp( void ){
    int i, j, k;
    bool bre;
    for( i=1; i<=tn; ++i )
    for( ; tot[i]; --tot[i] ){
         bre = true;
         for( j=tw; j>=w[i]; --j )
              if( (k=f[j-w[i]]+v[i]) > f[j] ){
                  f[j] = k; bre = false;
              }
         if( bre ) break;
    }
    return f[tw];
}