TopCoder SRM 192, DIV II, BoxLoader

Problem Statement

Your company has a new box loading robot. It is your job to program it to pack items into the shipping boxes. The robot does not have a very large program memory so you are restricted to placing all the items into the boxes in the same orientation. Each item is a rectangular solid with dimensions itemX by itemY by itemZ. The box is also rectangular with the dimensions boxX by boxY by boxZ. The items can be placed in the box in any orthogonal orientation (ie. the sides of the items must be parallel to the sides of the box), but only whole items can be placed in the box. Your task here is to determine the greatest number of items that can be packed into the box (with all the items in the same orientation).

For example, if the box is 100x98x81 units and the items are 3x5x7 units, then orienting the items so they are 5x7x3, allows them to fit in the box in a 20x14x27 grid, filling the entire box, which is optimal: 7560 items.


vector<int> items;
vector<int> boxes;

bool func (vector<int> ti, vector<int> tj){
  int mod1=0,mod2=0;
  repsz(i,ti){
    mod1 += boxes[i]%items[ti[i]];
    mod2 += boxes[i]%items[tj[i]];
  }
  return mod1<mod2;
}

class BoxLoader {

public:

int mostItems(int boxX, int boxY, int boxZ, int itemX, int itemY, int itemZ) {
 boxes.pb(boxX);
 boxes.pb(boxY);
 boxes.pb(boxZ);
 items.pb(itemX);
 items.pb(itemY);
 items.pb(itemZ);
 int cnt=0;
 repsz(i,items){
   cnt=0;
   repsz(j,boxes)
     if(items[i]>boxes[j])cnt++;
   if(cnt==3){boxes.clear();items.clear();return 0;}
 }
 vector<int> perm;
 perm.pb(0);
 perm.pb(1);
 perm.pb(2);
 vector<vector<int> > perms;
 perms.pb(perm);
 while(next_permutation(perm.begin(),perm.end())){
   perms.pb(perm);
 }
 sort(perms.begin(),perms.end(),func);
 perm = perms[0];
 int ans=1;
 repsz(i,perm){
   ans*=boxes[i]/items[perm[i]];
 }
 boxes.clear();items.clear();
 return ans;
}

};