2

問題は、合計が値になるすべてのサブセットを出力することです。可能なサブセットがあるかどうかを確認するコードを書きました。誰かが合計を形成する数字を印刷するアイデアを教えてくれますか. 以下は私のコードです。簡単にするために、配列には +ve nos のみが含まれていると仮定します。

void subsetsum(int A[], int target) {

int N = sizeof(A)/sizeof(int), sum = 0;

for(int i = 0; i < N; i++) sum += A[i];

vector<bool> V(sum + 1, 0);
V[0] = 1;
for(int i = 0; i < N; i++) 
   for(int j = sum; j >= 0; j--) {
      if(j + A[i] <= sum && V[j]) V[A[i] + j] = 1;
   }
  if(V[target]) cout << "Sumbset sum exists" << endl;
  else cout << "Sumbset sum doesnt exist" << endl;
}
4

4 に答える 4

1

a のベキ集合を求める関数vector<int>

vector<vector<int>> power_set(const vector<int>& nums) {
  if (nums.empty()) { return { {} }; }
  auto set = power_set(vector<int>(begin(nums) +1, end(nums)));
  auto tmp = set;
  for (auto& p : tmp) {
    p.push_back(nums[0]);
  }
  set.insert(end(set), begin(tmp), end(tmp));
  return set;
}

合計がターゲットになるベキ集合のすべての集合を返す関数

vector<vector<int>> test_sum(const vector<vector<int>>& ps, int target) {
  vector<vector<int>> v;
  for (auto& p : ps) {
    int sum = accumulate(begin(p), end(p), 0);
    if (sum == target) {
      v.push_back(p);
    }
  }
  return v;
}
于 2013-10-07T22:36:09.237 に答える
0

数字を出力するようにコードを変更しました。

void subsetsum(int A[], int target) {

    int N = sizeof(A) / sizeof(int), sum = 0;

    for (int i = 0; i < N; i++) sum += A[i];

    vector<bool> V(sum + 1, 0);
    V[0] = 1;
    for (int i = 0; i < N; i++)
        for (int j = sum; j >= 0; j--) {
            if (j + A[i] <= sum && V[j]) V[A[i] + j] = 1;
        }
    if (V[target]) cout << "Sumbset sum exists" << endl;
    else cout << "Sumbset sum doesnt exist" << endl;

    if (V[target])
    {
        for (int i = N - 1; i >= 0; i--)
        {
            if (V[target - A[i]] == 1) printf("%d, ", A[i]), target -= A[i];
        }
        printf("\n");
    }
}

またはこれが私のバージョンのベクトルです

bool subsetsum_dp(vector<int>& v, int sum)
{
    int n = v.size();
    const int MAX_ELEMENT = 100;
    const int MAX_ELEMENT_VALUE = 1000;
    static int dp[MAX_ELEMENT*MAX_ELEMENT_VALUE + 1]; memset(dp, 0, sizeof(dp));

    dp[0] = 1;

    for (int i = 0; i < n; i++)
    {
        for (int j = MAX_ELEMENT*MAX_ELEMENT_VALUE; j >= 0; j--)
        {
            if (j - v[i] < 0) continue;
            if (dp[j - v[i]]) dp[j] = 1;
        }
    }
    if (dp[sum])
    {
        for (int i = n - 1; i >= 0; i--)
        {
            if (dp[sum - v[i]] == 1) printf("%d, ", v[i]), sum -= v[i];
        }
        printf("\n");
    }

    return dp[sum] ? true : false;
}
于 2014-12-06T18:52:18.153 に答える