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

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

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

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

Answer 2

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

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

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

Answer 3

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