生成列表的功率集 [英] 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

虽然算法相当容易实现，但我没有丝毫的想法如何生成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;

我想为computeMaxProfit函数生成此列表的幂集。有没有一个算法来生成列表的子集？

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?

推荐答案

这是一个函数应该做的功夫：

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;
}

numPowerSets 马塞洛在此处提及的关系。正如 LiKao 所说，矢量似乎是自然的方式。当然，不要用大套尝试这样！

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!

这篇关于生成列表的功率集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！