10130: SuperSale

supersale.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*-----------------------------------------------------------------------------
 * Process the data 
 * 
 * input: 
 * v[i]: value of the ith object
 * wi[i]: weight of the ith object
 * mw[i]: maximal weight for ith person
 * 
 * output: the max value of objects that can be purchased
 *
 *----------------------------------------------------------------------------*/
void process(vector<int> & v, vector<int> & wi, vector<int> & mw) {
     int i, w, n, n_max = mw.size(), sum=0;
     for(n=0; n < n_max; n++) { 
         int N = v.size(); /* N: number of objects           */
         int MW = mw[n];   /* MW: maximum weight             */
         int c[N+1][MW+1]; /* c[value][weight] value matrix  */
         /* base-case: no items or zero-size sack            */
         for(i=0; i <= N; i++) c[i][0]=0;
         for(w=0; w <= MW; w++) c[0][w]=0;
         for(i=1; i <= N; i++) {
             for(w=1; w <= MW; w++) {
                 /* case 1: item i does not fit, so just use value
                    of the sack without item i */
                 if(wi[i-1] > w) c[i][w]=c[i-1][w];
                 /* case 2: item i fits, choose to keep or ignore */
                 else c[i][w] = max(c[i-1][w], c[i-1][w-wi[i-1]] + v[i-1]);
             }
         }
         sum += c[N][MW];    
     }
     cout << sum << endl;
}

int main () {
     int tc, items, ppl, tc_i, i, v, w;
     cin >> tc;
     for(tc_i=0;tc_i<tc;tc++) {
         vector<int> value;
         vector<int> weight;
         vector<int> people;
         cin >> items;
         for(i=0;i<items;i++) { 
             cin >> v >> w;
             value.push_back(v);
             weight.push_back(w);
         }
         cin >> ppl;
         for(i=0;i<ppl;i++) {
             cin >> w;
             people.push_back(w);
         }
         process(value,weight,people);
     }
     return 0;
}