Создание набора мощности списка

Question

Мне нужно написать грубую силу для проблемы с рюкзаком. Вот псевдокод:

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, и кормить подмножеств мощности, установленной на каждой итерации в то время как цикл.

Моя текущая реализация использует список пар, чтобы держать вес элемента и его прибыль:

list< pair<int, int> > weight_profit_pair; 

И я хочу, чтобы создать набор мощности этого списка для моей функции computeMaxProfit. Есть ли алгоритм для создания подмножеств списка? Является ли список подходящим контейнером для использования?

Answer 1

Вот пара функций, которые должны сделать трюк:

// 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, вектор кажется естественным путем. Конечно, не пробуйте это с большими наборами!

Answer 2

множества чисел S = {0, 1, 2, ..., 2 ^п - 1} образует набор мощности множества битов {1, 2, 4, ..., 2 ^{n - 1}}. Для каждого числа в наборе S выводите подмножество исходного набора, сопоставляя каждый бит числа с элементом из вашего набора. Поскольку итерация по всем 64-битным целым является неразрешимой, вы должны иметь возможность сделать это, не прибегая к библиотеке bigint.

Answer 3

Не используйте для этого список, но rathr любую структуру данных произвольного доступа, например. a std::vector. Если теперь у вас есть еще std::vector<bool>, вы можете использовать обе эти структуры вместе, чтобы представить элемент набора мощности. То есть если значение bool в позиции x истинно, то элемент в позиции x находится в подмножестве.

Теперь вам нужно перебрать все наборы в poweset. То есть вы генерируете следующее подмножество из каждого текущего подмножества, чтобы генерировались все наборы. Это просто счет в двоичном формате на std::vector<bool>.

Если в вашем наборе имеется менее 64 элементов, вы можете использовать длинные int вместо этого для подсчета, чтобы получить двоичное представление на каждой итерации.