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

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

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;

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


c++ knapsack-problem brute-force powerset
person nucleartide    schedule 12.02.2012    source источник

Ответы (3)


arrow_upward
2
arrow_downward

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

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

person Ben Hocking    schedule 12.02.2012
comment
Спасибо! Это очень помогло, честно говоря, мне потребовалась большая часть последних 4 часов, чтобы понять двоичные представления подмножеств. - person nucleartide; 13.02.2012

arrow_upward
2
arrow_downward

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

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

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

person LiKao    schedule 12.02.2012

arrow_upward
1
arrow_downward

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

person Marcelo Cantos    schedule 12.02.2012