商店购物1ac.cpp

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

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

int main(){
    int s, sp[100]={0}, ofc[100][6]={0}, ofk[100][6]={0};
    int f[6][6][6][6][6]={0}, n2buy[6]={0}, c2buy[6]={0}, p[6]={0};
    bool is2buy[1000]={true};
    int i, j, k;
    
    cin >>k;
    for( i=1; i<=k; ++i ){
         cin >>c2buy[i] >>n2buy[i] >>p[i];
         is2buy[ c2buy[i] ] = true;
    }
    
    cin >>s;
    for( i=1; i<=s; ++i ){
         cin >>k;
         for( j=1; j<=k; ++j ){
              cin >>ofc[i][j] >>ofk[i][j];
         }
         cin >>sp[i];
    }
    
    bool use[100]={0};
    for( i=1; i<=s; ++i )
         if( (is2buy[ofc[i][1]]) && (is2buy[ofc[i][2]]) && (is2buy[ofc[i][3]])
             && (is2buy[ofc[i][4]]) && (is2buy[ofc[i][5]]) )
             use[i] = true;
    
    int oc[100][6]={0}, ok[100][6]={0}, os=0, op[100]={0};
    for( i=1; i<=s; ++i )
         if( use[i] ){
             os++;
             op[os] = sp[i];
             for( j=1; j<=5; ++j )
             for( k=1; k<=5; ++k ){
                   if( ofc[i][k] == c2buy[j] ){
                       oc[os][j] = ofc[i][k];
                       ok[os][j] = ofk[i][k];
                   }
              }
         }
    
    int v[6], tem;
    bool notcon;
    for( v[1]=0; v[1]<=n2buy[1]; ++v[1] )
    for( v[2]=0; v[2]<=n2buy[2]; ++v[2] )
    for( v[3]=0; v[3]<=n2buy[3]; ++v[3] )
    for( v[4]=0; v[4]<=n2buy[4]; ++v[4] )
    for( v[5]=0; v[5]<=n2buy[5]; ++v[5] ){
         f[v[1]][v[2]][v[3]][v[4]][v[5]] = v[1]*p[1] + v[2]*p[2] + v[3]*p[3] + v[4]*p[4] + v[5]*p[5];
         for( i=1; i<=os; ++i ){
              notcon = true;
              for( j=1; j<=5; ++j )
                   if( v[j] < ok[i][j] ){
                       notcon = false;
                       break;
                   }
              if( !notcon ) continue;
              if( (tem=f[v[1]-ok[i][1]][v[2]-ok[i][2]][v[3]-ok[i][3]][v[4]-ok[i][4]][v[5]-ok[i][5]]+op[i])
                  < f[v[1]][v[2]][v[3]][v[4]][v[5]] )
                  f[v[1]][v[2]][v[3]][v[4]][v[5]] = tem;
         }
    }
    
    cout <<f[n2buy[1]][n2buy[2]][n2buy[3]][n2buy[4]][n2buy[5]] <<endl;
    system( "pause" );
    return 0;
}