Generating the power set of a list

Question

I have to write a brute-force implementation of the knapsack problem. Here's the pseudocode:

computeMaxProfit(weight_capacity)
    max_profit = 0
    S = {} // Each element of S is a weight-profit pair.
    while true
        if the sum of the weights in S <= weight_capacity
            if the sum of the profits in S > max_profit
                update max_profit
        if S contains all items // Then there is no next subset to generate
            return max
        generate the next subset S

While the algorithm is fairly easy to implement, I haven't the slightest idea how to generate the power set of S, and to feed the subsets of the power set into each iteration of the while loop.

My current implementation uses a list of pairs to hold an item's weight and profit:

list< pair<int, int> > weight_profit_pair;

And I want to generate the power set of this list for my computeMaxProfit function. Is there an algorithm out there to generate subsets of a list? Is a list the right container to use?

Answer 1

Here's a pair of functions that should do the trick:

// Returns which bits are on in the integer a                                                                                                                                                                                              
vector<int> getOnLocations(int a) {
  vector<int> result;
  int place = 0;
  while (a != 0) {
    if (a & 1) {
      result.push_back(place);
    }
    ++place;
    a >>= 1;
  }
  return result;
}

template<typename T>
vector<vector<T> > powerSet(const vector<T>& set) {
  vector<vector<T> > result;
  int numPowerSets = static_cast<int>(pow(2.0, static_cast<double>(set.size())));
  for (size_t i = 0; i < numPowerSets; ++i) {
    vector<int> onLocations = getOnLocations(i);
    vector<T> subSet;
    for (size_t j = 0; j < onLocations.size(); ++j) {
      subSet.push_back(set.at(onLocations.at(j)));
    }
    result.push_back(subSet);
  }
  return result;
}

The numPowerSets uses the relationship that Marcelo mentioned here. And as LiKao mentioned, a vector seems the natural way to go. Of course, don't try this with large sets!