Генерация набора мощности списка

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

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

list< pair<int, int> > weight_profit_pair;

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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