PNOI 2k8 Problem F: Shopping Spree

Problems from PNOI2008

Type: dynamic programming
Difficulty: medium-hard, tedious

Consider this the clarification-test problem: some pertinent upper limits were not given in the description: the maximum number of data sets (expected to be twenty, as the other problems); the maximum capacity of the cart; the maximum number of items. However, those not familiar with the core idea of the problem and its simplest solution would not know this, so it was more of a do-you-know-dynamic-programming problem.

Dynamic programming is actually a solution approach: you generate the solution by finding the solution to "smaller versions" of the problem you want to solve, and then build up solutions to "larger versions" from solutions to "smaller versions" until the solution to the original problem is achieved. The usual problem used to illustrate this approach is called the knapsack problem: given a knapsack of a particular capacity, and different items that each occupy a given space and have a given worth, what is the maximum worth that the knapsack can take? This particular problem has a small variation added: determine the number of each item that makes up this maximum worth.

However, the first - and more tedious problem - involves sorting the items by name. Sorting strings lexicographically is not really a trivial process: the comparison of strings is not as simple as the comparison of numbers. Add to this the difficulty that each item has three pieces of information that go with it: name, size and cost. These have to go together, as they define one item.

The best solution is to define an item structure/object (with get and set functions for each field) and defining a function to sort these items by name. The object in C++:

class Item {
  String name;
  int cost, size;
public:
  Item(String newName, int newCost, int newSize) {
    name = newName; 
    cost = newCost; 
    size = newSize;
  }
  String getName() {return name;}
  int getCost() {return cost;}
  int getSize() {return size;}
}

In cases where comparison between Strings isn't defined, here is a possible definition:

int compare(String str1, String str2) {
  int index;
  for (index = 0; str1.charAt(index) == str2.charAt(index); index ++);
  return str2.charAt(index) - str1.charAt(index);
}

The function returns a non-zero value, the difference between the first characters where the Strings are not the same: if it is positive, str2 comes after str1 in lexicographic order; if it is negative, the reverse. This function can be used as an argument for the predefined quicksort function in C/C++, or in your own sorting method.

Then, the dynamic programming approach can be applied: in this case, the maximum cost we can get for any cart size is where we get "smaller versions":

for (cartSize = 0; cartSize <= cartCapacity; cartSize ++) {
  maxCartCost[cartSize] = 0;
  for (item = 0; item < numOfItems; item ++) {
    if (cartSize >= items[item].getSize()) {
      costSmaller = maxCartCost[cartSize - items[item].getSize()];
      if (costSmaller + items[item].getCost() > maxCartCost[cartSize])
        maxCartCost[cartSize] = costSmaller + items[item].getCost();
    }
  }
}

Basically, for a given cartSize, for each item whose size is at least cartSize we determine if the currently stored maximum cost at cartSize is larger than [the maximum cost when the size of the cart was [cartSize minus the size of the item]] plus [the cost of that item]: if the sum is larger, the sum becomes the new value for the maximum cost at cartSize. After this loop ends, maxCartCost[cartCapacity] should have the maximum cost that can be taken in a cart that has capacity cartCapacity.

Now we have the total needed, but what were the items that composed the shopping cart to get that total? Here we "backtrack": using the same method to stock the shopping cart, we try to remove items one by one, until the cart is empty, as in:

for (item = 0; item < numOfItems; item ++)
  counts[item] = 0;
cartSize = cartCapacity;
while (cartSize > 0) {
  for (item = 0; item < numOfItems; item ++) {
    costSmaller = maxCartCost[cartSize - items[item].getSize()];
    if (costSmaller + items[item].getCost() == maxCartCost[cartSize])
      break;
  }
  counts[item] ++;
  cartSize -= items[item].getSize();
}