Generating the power set of a list

问题:

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?

回答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!

回答2:

Do not use a list for this, but rathr any kind of random access data structure, e.g. a std::vector. If you now have another std::vector<bool> you can use both these structures together to represent an element of the power set. I.e. if the bool at position x is true, then the element at position x is in the subset.

Now you have to iterate over all sets in the poweset. I.e. you have generate the next subset from each current subset, so that all sets are generated. This is just counting in binary on the std::vector<bool>.

If you have less than 64 elements in your set, you can use long ints instead for the counting an get the binary-representation at each iteration.

回答3:

The set of numbers S = {0, 1, 2, ..., 2ⁿ - 1} forms the power set of the set of bits {1, 2, 4, ..., 2^{n - 1}}. For each number in set S, derive a subset of your original set by mapping each bit of the number to an element from your set. Since iterating over all 64-bit integers is intractable, you should be able to do this without resorting to a bigint library.