C++でのパーティションの問題

この問題では、配列を2つの等しいサブ配列に分割できるかどうかを判断するためにC++コードを作成する必要があります。また、両方のサブ配列のすべての要素の合計が完全に同じであるかどうかを確認する必要があります。分割問題はサブセット和問題の変形であり、これはナップサック問題の変形です。パーティションの問題に取り組むために、C++プログラミング言語を使用します。指定された条件が満たされているかどうかに応じて、YesまたはNoの文字列を返す必要があります。

入力

arr[] = {6, 4, 8, 12, 15}

出力

Is possible to divide into two subsets of equal sum

問題を解決するためのアプローチ

目標は、セット内のすべての要素の合計を見つけることです。配列の合計が奇数の場合、2つのセットに分割することはできません。合計が偶数の場合、sum/2でサブセットを識別します。指定された配列を使用して、各要素を1つずつ調べてから、次のいずれかを選択します。

• 引き続き現在のアイテムをサブセットに含め、残りを追加して合計に到達します。

• 現在のアイテムがサブセットから削除されたら、他のアイテムに対してこのプロセスを繰り返します。

最後に、現在のアイテムがサブセットに含まれるか除外される場合はtrueを返します。それ以外の場合は、falseを返します。アイテムがなくなるか、合計が負になると、再帰は終了します。合計が0の場合、trueを返します。これは、サブセットが識別されたことを意味します。

例

#include <bits/stdc++.h>
using namespace std;
bool isSubsetSum(int arr[], int n, int sum) {
   if (sum == 0)
      return true;
   if (n == 0 && sum != 0)
      return false;
   if (arr[n - 1] > sum)
      return isSubsetSum(arr, n - 1, sum);
   return isSubsetSum(arr, n - 1, sum) ||
   isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
bool findPartiion(int arr[], int n) {
   int sum = 0;
   for (int i = 0; i < n; i++)
      sum += arr[i];
   if (sum % 2 != 0)
      return false;
   return isSubsetSum(arr, n, sum / 2);
}
int main() {
   int arr[] = {
      6,
      4,
      8,
      12,
      15
   };
   int n = sizeof(arr) / sizeof(arr[0]);
   if (findPartiion(arr, n) == true)
      cout << "Is possible to divide into two subsets " "of equal sum";
   else
      cout << "Is impossible to divide into two subsets" " of equal sum";
   return 0;
}

出力

Is impossible to divide into two subsets of equal sum

アプローチ2

コンポーネントの合計が大きすぎない場合は、動的計画法を使用して問題を処理できます。サイズ（sum / 2 + 1）*（n + 1）の2D配列part[][]を作成できます。また、下から上にソリューションを構築して、入力された各エントリが次のプロパティを持つようにすることもできます。この問題は、サイズの2次元配列（sum / 2 + 1）*（n + 1）を使用して解決できます。サイズの2次元配列（sum / 2 + 1）*（n + 1）。

例

#include <bits/stdc++.h>
using namespace std;
bool findPartiion(int arr[], int n) {
   int sum = 0;
   int i, j;
   for (i = 0; i < n; i++)
      sum += arr[i];
   if (sum % 2 != 0)
      return false;
   bool part[sum / 2 + 1];
   for (i = 0; i <= sum / 2; i++) {
      part[i] = 0;
   }
   for (i = 0; i < n; i++) {
      for (j = sum / 2; j >= arr[i]; j--){
         if (part[j - arr[i]] == 1 || j == arr[i])
            part[j] = 1;
      }
   }
   return part[sum / 2];
}
int main() {
   int arr[] = {
      6,
      4,
      8,
      12,
      15
   };
   int n = sizeof(arr) / sizeof(arr[0]);
   if (findPartiion(arr, n) == true)
      cout << "Is possible to divide into two subsets of equal " "sum";
   else
      cout << "Is impossible to divide into two subsets" " of equal sum";
   return 0;
}

出力

Is impossible to divide into two subsets of equal sum

結論

この問題では、c++コードとともにパーティションの問題を解決する方法を学びました。このコードは、Java、Python、およびその他の言語で作成することもできます。 C++プログラミング言語の再帰配列を使用してパーティションの問題を解決しました。これは基本的なコードですが、問題を解決するために多くの用途があります。