生成列表的功率集

我不得不写一个蛮力实现的背包问题。下面是伪代码：生成列表的功率集

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循环。

我的当前实现使用对列表持有一个项目的质量和利润：

list< pair<int, int> > weight_profit_pair;

我想产生的功率设定这个名单我computeMaxProfit功能。有没有算法来生成列表的子集？列表是否是正确的容器？

来源

2012-02-12 Jason Tu

这里有一对函数，应该做的伎俩：

// 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使用了马塞洛提到here的关系。正如LiKao提到的那样，矢量似乎是一种自然的方式。当然，不要试着用大套装！

来源

2012-02-12 21:53:15

谢谢！这有很大的帮助，它真的让我在过去的4个小时中了解了子集的二进制表示。 – 2012-02-13 02:08:02

数字集合S = {0,1,2，...，2 ⁿ_1}形成位集合{1,2,4，...，2的功率集合^{n - 1}}。对于集合S中的每个数字，通过将数字的每个位映射到您的集合中的一个元素来导出原始集合的子集。由于遍历所有64位整数是棘手的，因此您应该可以在不使用bigint库的情况下执行此操作。

来源

2012-02-12 21:39:20

不要为此使用列表，但不要使用任何类型的随机访问数据结构，例如，一个std::vector。如果您现在有另一个std::vector<bool>，则可以将这两个结构一起使用以表示功率集的一个元素。即如果位置x处的bool为真，则位置x处的元素在该子集中。

现在你必须迭代poweset中的所有集合。即您已经从每个当前子集中生成下一个子集，以便生成所有集合。这只是在二进制数std::vector<bool>。

如果您的集合中的元素少于64个，则可以使用long ints来计数并在每次迭代中获取二进制表示形式。

来源

2012-02-12 21:40:02 LiKao

生成列表的功率集

回答

相关问题