パーティションの問題
この問題では、各サブセットの合計が等しくなるように、特定のセットを分割できます。
最初に、与えられたセットの合計を見つける必要があります。偶数の場合は、2つのセットに分割する可能性があります。それ以外の場合は分割できません。
合計の値が偶数の場合は、partTableという名前のテーブルを作成し、次の条件を使用して問題を解決します。
partTable [i、j]は、array[0]からarray[j-1]へのサブセットの合計がiに等しい場合は真、それ以外の場合は偽です。
入力と出力
Input: A set of integers. {3, 1, 1, 2, 2, 1} Output: True if the set can be partitioned into two parts with equal sum. Here the answer is true. One pair of the partitions are: {3, 1, 1}, {2, 2, 1}です。
アルゴリズム
checkPartition(set, n)
入力- 指定されたセット、セット内の要素の数。
出力- 分割によって等しい合計の2つのサブセットを作成できる場合はTrue。
Begin sum := sum of all elements in the set if sum is odd, then return define partTable of order (sum/2 + 1 x n+1) set all elements in the 0th row to true set all elements in the 0th column to false for i in range 1 to sum/2, do for j in range 1 to n, do partTab[i, j] := partTab[i, j-1] if i >= set[j-1], then partTab[i, j] := partTab[i, j] or with partTab[i – set[j-1], j-1] done done return partTab[sum/2, n] End
例
#include <iostream> using namespace std; bool checkPartition (int set[], int n) { int sum = 0; for (int i = 0; i < n; i++) //find the sum of all elements of set sum += set[i]; if (sum%2 != 0) //when sum is odd, it is not divisible into two set return false; bool partTab[sum/2+1][n+1]; //create partition table for (int i = 0; i <= n; i++) partTab[0][i] = true; //for set of zero element, all values are true for (int i = 1; i <= sum/2; i++) partTab[i][0] = false; //as first column holds empty set, it is false // Fill the partition table in botton up manner for (int i = 1; i <= sum/2; i++) { for (int j = 1; j <= n; j++) { partTab[i][j] = partTab[i][j-1]; if (i >= set[j-1]) partTab[i][j] = partTab[i][j] || partTab[i - set[j-1]][j-1]; } } return partTab[sum/2][n]; } int main() { int set[] = {3, 1, 1, 2, 2, 1}; int n = 6; if (checkPartition(set, n)) cout << "Given Set can be divided into two subsets of equal sum."; else cout << "Given Set can not be divided into two subsets of equal sum."; }
出力
Given Set can be divided into two subsets of equal sum.
-
頂点被覆問題
無向グラフの場合、頂点被覆は頂点のサブセットであり、グラフのすべてのエッジ(u、v)について、uまたはvのいずれかがセットに含まれます。 二分木を使用すると、頂点被覆問題を簡単に解決できます。 この問題は、2つのサブ問題に分けることができます。ルートが頂点被覆の一部である場合。この場合、ルートはすべての子エッジをカバーします。左右のサブツリーの頂点被覆のサイズを簡単に見つけて、ルートに1を追加できます。 入力と出力 Input: A binary tree. Output: The vertex cover is 3. アルゴリズム vertexCover(root node
-
C++でセットをk個のサブセットに分割する方法の数を数えます
与えられた2つの数字eとp。目標は、セットのe個の要素をp個のパーティション/サブセットに分割できる方法の数を数えることです。 例 入力 e=4 p=2 出力 Count of number of ways to partition a set into k subsets are: 7 説明 If elements are: a b c d then ways to divide them into 2 partitions are: (a,b,c)−(d), (a,b)−(c,d), (a,b,c)−(d), (a)−(b,c,d), (