生成列表的功率集

我不得不寫一個蠻力實現的揹包問題。下面是僞代碼：生成列表的功率集

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

生成列表的功率集

回答

相關問題