金明预算.cpp

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

#include <iostream>
using namespace std;

int main(){
    const int M = 70;
    int tot[M]={0}, price[M][3]={0}, value[M][3]={0}, n, m, v, p, q, i, j;
    bool zj[M]={0};
    const int N = 3210;
    int f[N]={0};
    cin >>n >>m;
    n /= 10;
    for( i=1; i<=m; ++i ){
         cin >>v >>p >>q;
         v /= 10;
         if( q ){
             ++tot[q];
             price[q][tot[q]] = v;
             value[q][tot[q]] = v * p ;
         }
         else{
             price[i][0] = v;
             value[i][0] = v * p ;
             zj[i] = true;
         }
    }
    
    for( i=1; i<=m; ++i )
         if( zj[i] ){
             for( j=n; j>=price[i][0]; --j ){
                  if( (p=f[j-price[i][0]]+value[i][0]) > f[j] ) f[j] = p;
                  if( (j>=price[i][0]+price[i][1])
                      && ( (p=f[j-price[i][0]-price[i][1]]+value[i][0]+value[i][1])>f[j]) )
                      f[j] = p;
                  if( (j>=price[i][0]+price[i][2])
                      && ( (p=f[j-price[i][0]-price[i][2]]+value[i][0]+value[i][2])>f[j]) )
                      f[j] = p;
                  if( (j>=price[i][0]+price[i][1]+price[i][2])
                      && ( (p=f[j-price[i][0]-price[i][1]-price[i][2]]+value[i][0]+value[i][1]+value[i][2])>f[j]) )
                      f[j] = p;
             }
         }
    
    cout <<f[n]*10 <<endl;
    system( "pause" );
    return 0;
}