Проблема разделения состоит в том, чтобы определить, можно ли разбить данный набор на два подмножества так, чтобы сумма элементов в обоих подмножествах была одинаковой.
Примеры:
arr[] = {1, 5, 11, 5}
Output: true
The array can be partitioned as {1, 5, 5} and {11}
arr[] = {1, 5, 3}
Output: false
The array cannot be partitioned into equal sum sets.
Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.
Ниже приведены два основных шага для решения этой проблемы: 1) Рассчитать сумму массива. Если сумма нечетная, не может быть двух подмножеств с равной суммой, поэтому верните false. 2) Если сумма элементов массива четная, вычислите сумму / 2 и найдите подмножество массива с суммой, равной сумме / 2.
Первый шаг прост. Второй шаг очень важен, его можно решить с помощью рекурсии или динамического программирования.
Рекурсивное решение Ниже приведено рекурсивное свойство второго этапа, упомянутого выше.
Let isSubsetSum(arr, n, sum/2) be the function that returns true if
there is a subset of arr[0..n-1] with sum equal to sum/2
The isSubsetSum problem can be divided into two subproblems
a) isSubsetSum() without considering last element
(reducing n to n-1)
b) isSubsetSum considering the last element
(reducing sum/2 by arr[n-1] and n to n-1)
If any of the above the above subproblems return true, then return true.
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
isSubsetSum (arr, n-1, sum/2 - arr[n-1])
C ++
// Рекурсивная программа на C ++ для решения проблем с разделами #include <bits/stdc++.h>
usingnamespacestd;
// Сервисная функция, которая возвращает true, если есть // подмножество arr [] с солнцем, равным данной сумме
boolisSubsetSum (intarr[], intn, intsum)
{
// Базовые случаи
if(sum == 0)
returntrue;
if(n == 0 && sum != 0)
returnfalse;
// Если последний элемент больше суммы, то
// игнорируй это
if(arr[n-1] > sum)
returnisSubsetSum (arr, n-1, sum);
/ * иначе, проверьте, может ли сумма быть получена любым из
следующее
(а) включая последний элемент
(б) исключая последний элемент
* /
returnisSubsetSum (arr, n-1, sum) ||
isSubsetSum (arr, n-1, sum-arr[n-1]);
}
// Возвращает true, если arr [] можно разбить на два // подмножества равной суммы, иначе ложь
boolfindPartiion (intarr[], intn)
{
// Вычисляем сумму элементов в массиве
intsum = 0;
for(inti = 0; i < n; i++)
sum += arr[i];
// Если сумма нечетная, не может быть двух подмножеств
// с равной суммой
if(sum%2 != 0)
returnfalse;
// Найти, есть ли подмножество с суммой, равной
// половина общей суммы
returnisSubsetSum (arr, n, sum/2);
}
// Программа драйвера для проверки вышеуказанной функции
intmain()
{
intarr[] = {3, 1, 5, 9, 12};
intn = sizeof(arr)/sizeof(arr[0]);
if(findPartiion(arr, n) == true)
cout << "Can be divided into two subsets "
"of equal sum";
else
cout << "Can not be divided into two subsets"
" of equal sum";
return0;
}
// Этот код предоставлен rathbhupendra
С
// Рекурсивная программа на C для проблемы с разделами #include <stdio.h> #include <stdbool.h>
// Сервисная функция, которая возвращает true, если есть // подмножество arr [] с солнцем, равным данной сумме
boolisSubsetSum (intarr[], intn, intsum)
{
// Базовые случаи
if(sum == 0)
returntrue;
if(n == 0 && sum != 0)
returnfalse;
// Если последний элемент больше суммы, то
// игнорируй это
if(arr[n-1] > sum)
returnisSubsetSum (arr, n-1, sum);
/ * иначе, проверьте, может ли сумма быть получена любым из
следующее
(а) включая последний элемент
(б) исключая последний элемент
* /
returnisSubsetSum (arr, n-1, sum) ||
isSubsetSum (arr, n-1, sum-arr[n-1]);
}
// Возвращает true, если arr [] можно разбить на два // подмножества равной суммы, иначе ложь
boolfindPartiion (intarr[], intn)
{
// Вычисляем сумму элементов в массиве
intsum = 0;
for(inti = 0; i < n; i++)
sum += arr[i];
// Если сумма нечетная, не может быть двух подмножеств
// с равной суммой
if(sum%2 != 0)
returnfalse;
// Найти, есть ли подмножество с суммой, равной
// половина общей суммы
returnisSubsetSum (arr, n, sum/2);
}
// Программа драйвера для проверки вышеуказанной функции
intmain()
{
intarr[] = {3, 1, 5, 9, 12};
intn = sizeof(arr)/sizeof(arr[0]);
if(findPartiion(arr, n) == true)
printf("Can be divided into two subsets "
"of equal sum");
else
printf("Can not be divided into two subsets"
" of equal sum");
return0;
}
Джава
// Рекурсивное решение Java для проблемы разбиения
importjava.io.*;
classPartition
{
// Сервисная функция, которая возвращает true, если есть
// подмножество arr [] с солнцем, равным данной сумме
staticbooleanisSubsetSum (intarr[], intn, intsum)
{
// Базовые случаи
if(sum == 0)
returntrue;
if(n == 0&& sum != 0)
returnfalse;
// Если последний элемент больше суммы, тогда игнорируем его
if(arr[n-1] > sum)
returnisSubsetSum (arr, n-1, sum);
/ * иначе, проверьте, может ли сумма быть получена любым из
следующее
(а) включая последний элемент
(б) исключая последний элемент
* /
returnisSubsetSum (arr, n-1, sum) ||
isSubsetSum (arr, n-1, sum-arr[n-1]);
}
// Возвращает true, если arr [] можно разбить на два
// подмножества равной суммы, иначе ложь
staticbooleanfindPartition (intarr[], intn)
{
// Вычисляем сумму элементов в массиве
intsum = 0;
for(inti = 0; i < n; i++)
sum += arr[i];
// Если сумма нечетная, не может быть двух подмножеств
// с равной суммой
if(sum%2!= 0)
returnfalse;
// Найти, есть ли подмножество с суммой, равной половине
// от общей суммы
returnisSubsetSum (arr, n, sum/2);
}
/ * Функция драйвера для проверки вышеуказанной функции * /
publicstaticvoidmain (String[] args)
{
intarr[] = {3, 1, 5, 9, 12};
intn = arr.length;
if(findPartition(arr, n) == true)
System.out.println("Can be divided into two "+
"subsets of equal sum");
else
System.out.println("Can not be divided into "+
"two subsets of equal sum");
}
} / * Этот код предоставлен Девешом Агравалом * /
python3
# Рекурсивная программа на Python3 для # проблема с разделом
# Сервисная функция, которая возвращает # true, если есть подмножество # arr [] с солнцем, равным заданной сумме
defisSubsetSum (arr, n, sum):
# Базовые случаи
ifsum==0:
returnTrue
ifn ==0andsum!=0:
returnFalse
# Если последний элемент больше суммы, то
# игнорируй это
ifarr[n-1] > sum:
returnisSubsetSum (arr, n-1, sum)
'' 'иначе, проверьте, может ли сумма быть получена любым из
# Возвращает true, если arr [] можно разбить на два # подмножества равной суммы, иначе ложь
deffindPartion (arr, n):
# Рассчитать сумму элементов в массиве
sum=0
fori inrange(0, n):
sum+=arr[i]
# Если сумма нечетная, не может быть двух подмножеств
# с равной суммой
ifsum%2!=0:
returnfalse
# Найти, есть ли подмножество с суммой, равной
# половина от общей суммы
returnisSubsetSum (arr, n, sum//2)
# Программа драйвера для проверки вышеуказанной функции
arr =[3, 1, 5, 9, 12]
n =len(arr)
iffindPartion(arr, n) ==True:
print("Can be divided into two subsets of equal sum")
else:
print("Can not be divided into two subsets of equal sum")
# Этот код предоставлен shreyanshi_arun.
C #
// Рекурсивное решение C # для проблемы разбиения
usingSystem;
classGFG
{
// Сервисная функция, которая возвращает true, если есть
// подмножество arr [] с солнцем, равным данной сумме
staticboolisSubsetSum (int[]arr, intn, intsum)
{
// Базовые случаи
if(sum == 0)
returntrue;
if(n == 0 && sum != 0)
returnfalse;
// Если последний элемент больше суммы, тогда игнорируем его
if(arr[n-1] > sum)
returnisSubsetSum (arr, n-1, sum);
/ * иначе, проверьте, может ли сумма быть получена любым из
следующее
(а) включая последний элемент
(б) исключая последний элемент
* /
returnisSubsetSum (arr, n-1, sum) ||
isSubsetSum (arr, n-1, sum-arr[n-1]);
}
// Возвращает true, если arr [] можно разбить на два
// подмножества равной суммы, иначе ложь
staticboolfindPartition (int[]arr, intn)
{
// Вычисляем сумму элементов в массиве
intsum = 0;
for(inti = 0; i < n; i++)
sum += arr[i];
// Если сумма нечетная, не может быть двух подмножеств
// с равной суммой
if(sum%2 != 0)
returnfalse;
// Найти, есть ли подмножество с суммой, равной половине
// от общей суммы
returnisSubsetSum (arr, n, sum/2);
}
// Функция драйвера
publicstaticvoidMain ()
{
int[]arr = {3, 1, 5, 9, 12};
intn = arr.Length;
if(findPartition(arr, n) == true)
Console.Write("Can be divided into two "+
"subsets of equal sum");
else
Console.Write("Can not be divided into "+
"two subsets of equal sum");
}
}
// Этот код предоставлен Sam007
PHP
<?php // Рекурсивное решение PHP для проблемы с разделами
// Сервисная функция, которая возвращает true, если есть // подмножество arr [] с солнцем, равным данной сумме
functionisSubsetSum ($arr, $n, $sum)
{
// Базовые случаи
if($sum== 0)
returntrue;
if($n== 0 && $sum!= 0)
returnfalse;
// Если последний элемент больше чем
// сумма, затем игнорируем
if($arr[$n- 1] > $sum)
returnisSubsetSum ($arr, $n- 1, $sum);
/ * иначе, проверьте, можно ли получить сумму
любым из следующих
(а) включая последний элемент
(б) исключая последний элемент
* /
returnisSubsetSum ($arr, $n- 1, $sum) ||
isSubsetSum ($arr, $n- 1,
$sum- $arr[$n- 1]);
}
// Возвращает true, если arr [] может быть разделен // в двух подмножествах равной суммы, в противном случае ложь
functionfindPartiion ($arr, $n)
{
// Рассчитать сумму элементов
// в массиве
$sum= 0;
for($i= 0; $i< $n; $i++)
$sum+= $arr[$i];
// Если сумма нечетная, не может быть
// два подмножества с равной суммой
if($sum% 2 != 0)
returnfalse;
// Найти, есть ли подмножество с суммой
// равно половине общей суммы
returnisSubsetSum ($arr, $n, $sum/ 2);
}
// Код драйвера
$arr= array(3, 1, 5, 9, 12);
$n= count($arr);
if(findPartiion($arr, $n) == true)
echo"Can be divided into two subsets of equal sum";
else
echo"Can not be divided into two subsets of equal sum";
// Этот код предоставлен rathbhupendra ?>
Выход:
Can be divided into two subsets of equal sum
Сложность времени: O (2 ^ n) В худшем случае это решение пробует две возможности (включить или исключить) для каждого элемента.
Решение для динамического программирования Проблема может быть решена с помощью динамического программирования, когда сумма элементов не слишком велика. Мы можем создать часть 2D-массива [] [] размера (sum / 2) * (n + 1). И мы можем построить решение снизу вверх так, чтобы каждая заполненная запись имела следующее свойство
part[i][j] = true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum
equal to i, otherwise false
C ++
// Динамическое программирование на основе // C ++ программа для разделения раздела #include <bits/stdc++.h>
usingnamespacestd;
// Возвращает true, если arr [] может быть разделен // в двух подмножествах равной суммы, в противном случае ложь
boolfindPartiion (intarr[], intn)
{
intsum = 0;
inti, j;
// Рассчитать сумму всех элементов
for(i = 0; i < n; i++)
sum += arr[i];
if(sum % 2 != 0)
returnfalse;
boolpart[sum / 2 + 1][n + 1];
// инициализировать верхнюю строку как true
for(i = 0; i <= n; i++)
part[0][i] = true;
// инициализируем крайний левый столбец,
// кроме part [0] [0], как 0
for(i = 1; i <= sum / 2; i++)
part[i][0] = false;
// Заполняем таблицу разделов снизу вверх
for(i = 1; i <= sum / 2; i++)
{
for(j = 1; j <= n; j++)
{
part[i][j] = part[i][j - 1];
if(i >= arr[j - 1])
part[i][j] = part[i][j] ||
part[i - arr[j - 1]][j - 1];
}
}
/ * // раскомментируем эту часть для печати таблицы
для (i = 0; i <= sum / 2; i ++)
{
для (j = 0; j <= n; j ++)
соиЬ << часть [я] [J];
соиЬ << епсИ;
} * /
returnpart[sum / 2][n];
}
// Код драйвера
intmain()
{
intarr[] = {3, 1, 1, 2, 2, 1};
intn = sizeof(arr) / sizeof(arr[0]);
if(findPartiion(arr, n) == true)
cout << "Can be divided into two subsets of equal sum";
else
cout << "Can not be divided into"
<< " two subsets of equal sum";
return0;
}
// Этот код предоставлен rathbhupendra
С
// Программа C на основе динамического программирования для разделения задачи #include <stdio.h>
// Возвращает true, если arr [] можно разбить на два подмножества // равная сумма, иначе ложь
boolfindPartiion (intarr[], intn)
{
intsum = 0;
inti, j;
// Рассчитать сумму всех элементов
for(i = 0; i < n; i++)
sum += arr[i];
if(sum%2 != 0)
returnfalse;
boolpart[sum/2+1][n+1];
// инициализировать верхнюю строку как true
for(i = 0; i <= n; i++)
part[0][i] = true;
// инициализируем крайний левый столбец, кроме part [0] [0], как 0
/ * // раскомментируем эту часть для печати таблицы
для (i = 0; i <= sum / 2; i ++)
{
для (j = 0; j <= n; j ++)
printf ("% 4d", часть [i] [j]);
Е ( "/ п");
} * /
returnpart[sum/2][n];
}
// Программа драйвера для проверки вышеуказанной функции
intmain()
{
intarr[] = {3, 1, 1, 2, 2, 1};
intn = sizeof(arr)/sizeof(arr[0]);
if(findPartiion(arr, n) == true)
printf("Can be divided into two subsets of equal sum");
else
printf("Can not be divided into two subsets of equal sum");
getchar();
return0;
}
Джава
// Java-программа на основе динамического программирования для решения проблемы секционирования
importjava.io.*;
classPartition {
// Возвращает true, если arr [] можно разбить на два подмножества
// равная сумма, иначе ложь
staticbooleanfindPartition (intarr[], intn)
{
intsum = 0;
inti, j;
// Рассчитать сумму всех элементов
for(i = 0; i < n; i++)
sum += arr[i];
if(sum%2!= 0)
returnfalse;
booleanpart[][]=newboolean[sum/2+1][n+1];
// инициализировать верхнюю строку как true
for(i = 0; i <= n; i++)
part[0][i] = true;
// инициализируем крайний левый столбец, кроме part [0] [0], как 0
for(i = 1; i <= sum/2; i++)
part[i][0] = false;
// Заполняем таблицу разделов снизу вверх
for(i = 1; i <= sum/2; i++)
{
for(j = 1; j <= n; j++)
{
part[i][j] = part[i][j-1];
if(i >= arr[j-1])
part[i][j] = part[i][j] ||
part[i - arr[j-1]][j-1];
}
}
/ * // раскомментируем эту часть для печати таблицы
для (i = 0; i <= sum / 2; i ++)
{
для (j = 0; j <= n; j ++)
printf ("% 4d", часть [i] [j]);
Е ( "/ п");
} * /
returnpart[sum/2][n];
}
/ * Функция драйвера для проверки вышеуказанной функции * /
publicstaticvoidmain (String[] args)
{
intarr[] = {3, 1, 1, 2, 2,1};
intn = arr.length;
if(findPartition(arr, n) == true)
System.out.println("Can be divided into two "
"subsets of equal sum");
else
System.out.println("Can not be divided into"
" two subsets of equal sum");
}
} / * Этот код предоставлен Девешом Агравалом * /
python3
# Динамическое программирование на основе Python # программа для разделения раздела
# Возвращает true, если arr [] может быть # разбит на два подмножества # равная сумма, иначе ложь
deffindPartition(arr, n):
sum=0
i, j =0, 0
# вычислить сумму всех элементов
fori inrange(n):
sum+=arr[i]
ifsum%2!=0:
returnfalse
part =[[ Truefori inrange(n +1)]
forj inrange(sum//2+1)]
# инициализировать верхнюю строку как true
fori inrange(0, n +1):
part[0][i] =True
# инициализировать крайний левый столбец,
# кроме части [0] [0], как 0
fori inrange(1, sum//2+1):
part[i][0] =False
# заполнить таблицу разделов в
# снизу вверх
fori inrange(1, sum//2+1):
forj inrange(1, n +1):
part[i][j] =part[i][j -1]
ifi >=arr[j -1]:
part[i][j] =(part[i][j] or
part[i -arr[j -1]][j -1])
returnpart[sum//2][n]
Код водителя
arr =[3, 1, 1, 2, 2, 1]
n =len(arr)
iffindPartition(arr, n) ==True:
print("Can be divided into two",
"subsets of equal sum")
else:
print("Can not be divided into ",
"two subsets of equal sum")
# Этот код добавлен # от mohit kumar 29
C #
// Программа C # на основе динамического программирования // для проблемы с разделом
usingSystem;
classGFG {
// Возвращает true, если arr [] может быть разделен
// в двух подмножествах равной суммы, в противном случае
// ложный
staticboolfindPartition (int[]arr, intn)
{
intsum = 0;
inti, j;
// Рассчитать сумму всех элементов
for(i = 0; i < n; i++)
sum += arr[i];
if(sum % 2 != 0)
returnfalse;
bool[, ]part=newbool[sum / 2 + 1, n + 1];
// инициализировать верхнюю строку как true
for(i = 0; i <= n; i++)
part[0, i] = true;
// инициализируем крайний левый столбец, кроме
// part [0] [0], как 0
for(i = 1; i <= sum/2; i++)
part[i, 0] = false;
// Заполняем таблицу разделов в нижней части
// вверх
for(i = 1; i <= sum/2; i++)
{
for(j = 1; j <= n; j++)
{
part[i, j] = part[i, j - 1];
if(i >= arr[j - 1])
part[i, j] = part[i, j - 1] ||
part[i - arr[j - 1],j - 1];
}
}
/ * // раскомментируем эту часть для печати таблицы
для (i = 0; i <= sum / 2; i ++)
{
для (j = 0; j <= n; j ++)
printf ("% 4d", часть [i] [j]);
Е ( "/ п");
} * /
returnpart[sum / 2, n];
}
// Программа драйвера для проверки вышеуказанной функции
publicstaticvoidMain ()
{
int[]arr = {3, 1, 1, 2, 2,1};
intn = arr.Length;
if(findPartition(arr, n) == true)
Console.Write("Can be divided"
+ " into two subsets of"
+ " equal sum");
else
Console.Write("Can not be "
+ "divided into two subsets"
+ " of equal sum");
}
}
// Этот код предоставлен Sam007.
Выход:
Can be divided into two subsets of equal sum
Следующая диаграмма показывает значения в таблице разделов.
Сложность времени: O (сумма * n) Вспомогательное пространство: O (сумма * n) Обратите внимание, что это решение не подходит для массивов с большой суммой.