Pages

Thursday, August 12, 2010

TC SRM 487 D1-500 KiwiJuice

Category: Dynamic Programming
URL: http://www.topcoder.com/stat?c=problem_statement&pm=11019


class KiwiJuice {
public:
   int theProfit(int, vector <int>, vector <int>);
};

int dp[51][1<<16];
vector<int> data;
vector<int> price;
int _C;

// f(current volume of the special bottle, bitmask of the used bottles)
int f(int i, int mask) {
   // caching mechanism
   if (dp[i][mask] != -1) return dp[i][mask];
   // base case
   if (mask+1 == (1 << (data.size()))-1) {
      return price[i];
   }
   int res = 0;
   for (int j = 1; j < data.size(); j++) {
      if (mask & (1 << j)) continue;   // already used
      // the next bottle to process
      int next = data[j];
      int d1 = 0;
      if (i + next >= _C) {
         // one of the bottles is full, the other is i+next-_C volume
         d1 = price[_C] + f(i+next-_C, mask | (1 << j));
      } else {
         // change to i + next (and used up the empty for bottle[j])
         d1 = price[0] + f(i+next, mask | (1 << j));
      }
      // don't add more to our current bottle
      // we swap with bottle j and "use" up our bottle
      int d2 = f(next, mask | (1 << j)) + price[i];
      
      // take the maximum of the decision branches
      res >?= max(d1,d2);
   }
   return dp[i][mask] = res;
}

int KiwiJuice::theProfit(int C, vector <int> bottles, vector <int> prices) {
   price = prices;
   int res = 0;
   _C = C;
   memset(dp,-1,sizeof(dp));
   data = bottles;
   return res = f(data[0],0);   // arbitrarily assign bottle 0 to be our special bottle
}

6 comments:

  1. Overall you did an amazing job with the post. I like where your ideology about the professional assignment help services is going. When planning to order your assignments from a reliable portal, you should try the Thesis Writing Help facilities by the MyAssignmentHelpAU platform. You will receive flawless assignment solutions that can easily grab the highest possible scores for you in the shortest possible turnarounds.

    ReplyDelete