商店购物2ac.cpp

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

// 先商品，后优惠 
#include <iostream>
using namespace std;

const int D = 6;

const int TYH = 101;
struct Yh{
       bool use;
       int c[D], k[D], p;
};
int tyh;
Yh yh[TYH];
void InputYh( void );             // tyh, yh

struct Sp{
       int tsp, c[D], k[D], p[D];
};
Sp sp;
void InputSp( void );             // sp

const int TCODE = 1002;
int code[TCODE]={0};
void CheckYhUse( void );

int ts, s[TYH][D]={0}, f[D][D][D][D][D]={0};
void GetS( void );
int Dp( void );

int main(){
    InputSp();
    InputYh();
    CheckYhUse();
    GetS();
    cout <<Dp() <<endl;
    system( "pause" );
    return 0;
}

void InputYh( void ){
     cin >>tyh;
     int i, j, n;
     for( i=1; i<=tyh; ++i ){
          cin >>n;
          for( j=1; j<=n; ++j )
               cin >>yh[i].c[j] >>yh[i].k[j];
          cin >>yh[i].p;
          for( ; j<=5; ++j )
               yh[i].c[j] = yh[i].k[j] = 0;
          yh[i].use = true;
     }
     return;
}

void InputSp( void ){
     int i;
     cin >>sp.tsp;
     for( i=1; i<=sp.tsp; ++i ){
          cin >>sp.c[i] >>sp.k[i] >>sp.p[i];
     }
     for( ; i<=5; ++i )
          sp.c[i] = sp.k[i] = sp.p[i] = 0;
     return;
}

void CheckYhUse( void ){
     int i, j;
     for( i=1; i<=sp.tsp; ++i )
          code[sp.c[i]] = i;
     code[0] = D;
     for( i=1; i<=tyh; ++i )
     for( j=1; j<=5; ++j )
          if( code[yh[i].c[j]] == 0 ){
              yh[i].use = false; break;
          }
     return;
}

void GetS( void ){
     ts = 0;
     int i, j, k;
     for( i=1; i<=tyh; ++i )
     if( yh[i].use ){
         ++ts;
         for( j=1; j<=5; ++j )
         for( k=1; k<=5; ++k )
              if( code[yh[i].c[k]] == j )
                  s[ts][j] = yh[i].k[k];
         s[ts][0] = yh[i].p;
     }
     return;
}

int Dp( void ){
    int i[D], j, k;
    for( i[1]=sp.k[1]; i[1]>=0; --i[1] )
    for( i[2]=sp.k[2]; i[2]>=0; --i[2] )
    for( i[3]=sp.k[3]; i[3]>=0; --i[3] )
    for( i[4]=sp.k[4]; i[4]>=0; --i[4] )
    for( i[5]=sp.k[5]; i[5]>=0; --i[5] )
         f[i[1]][i[2]][i[3]][i[4]][i[5]] = i[1]*sp.p[1] + i[2]*sp.p[2]
                                         + i[3]*sp.p[3] + i[4]*sp.p[4] + i[5]*sp.p[5];
    
    for( j=1; j<=ts; ++j )
    for( i[1]=0; i[1]<=sp.k[1]; ++i[1] )
    for( i[2]=0; i[2]<=sp.k[2]; ++i[2] )
    for( i[3]=0; i[3]<=sp.k[3]; ++i[3] )
    for( i[4]=0; i[4]<=sp.k[4]; ++i[4] )
    for( i[5]=0; i[5]<=sp.k[5]; ++i[5] ){
         if( (i[1]>=s[j][1]) && (i[2]>=s[j][2])
             && (i[3]>=s[j][3]) && (i[4]>=s[j][4]) && (i[5]>=s[j][5])
             && (  f[i[1]][i[2]][i[3]][i[4]][i[5]]
                   > ( k = f[i[1]-s[j][1]][i[2]-s[j][2]][i[3]-s[j][3]][i[4]-s[j][4]][i[5]-s[j][5]]
                           + s[j][0]
                     )
                )
           )
         f[i[1]][i[2]][i[3]][i[4]][i[5]] = k;
    }
    
    return f[sp.k[1]][sp.k[2]][sp.k[3]][sp.k[4]][sp.k[5]];
}