3

ナップサック問題のブルートフォース実装を作成する必要があります。擬似コードは次のとおりです。

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関数用にこのリストのべき集合を生成したいと思います。リストのサブセットを生成するためのアルゴリズムはありますか？リストは使用するのに適切なコンテナですか？

4

3 に答える 3

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が述べたように、ベクトルは自然な方法のようです。もちろん、大きなセットでこれを試さないでください！

于 2012-02-12T21:53:15.620 に答える
2

このためにリストを使用するのではなく、任意の種類のランダムアクセスデータ構造を使用してくださいstd::vector。別のものがあるstd::vector<bool>場合は、これらの両方の構造を一緒に使用して、べき集合の要素を表すことができます。つまり、boolat位置xがtrueの場合、位置の要素xはサブセットに含まれます。

ここで、パワーセット内のすべてのセットを反復処理する必要があります。つまり、すべてのセットが生成されるように、現在の各サブセットから次のサブセットを生成する必要があります。これは、でバイナリでカウントしているだけstd::vector<bool>です。

セットに含まれる要素が64未満の場合は、カウントの代わりにlong intを使用して、各反復でバイナリ表現を取得できます。

于 2012-02-12T21:40:02.190 に答える
1

数値のセットS={0、1、2、...、2 n --1}は、ビットのセット{1、2、4、...、2n-1}のべき集合を形成します。セットSの各数値について、数値の各ビットをセットの要素にマッピングすることにより、元のセットのサブセットを導出します。すべての64ビット整数を反復処理するのは難しいため、bigintライブラリを使用せずにこれを実行できるはずです。

于 2012-02-12T21:39:20.277 に答える