Рубрики

Проблема с разделами | DP-18

Проблема разделения состоит в том, чтобы определить, можно ли разбить данный набор на два подмножества так, чтобы сумма элементов в обоих подмножествах была одинаковой.

Примеры:

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>

using namespace std;

  
// Сервисная функция, которая возвращает true, если есть
// подмножество arr [] с солнцем, равным данной сумме

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]); 

  
// Возвращает true, если arr [] можно разбить на два
// подмножества равной суммы, иначе ложь

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[] = {3, 1, 5, 9, 12}; 

    int n = 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"

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Рекурсивная программа на C для проблемы с разделами
#include <stdio.h>
#include <stdbool.h>

  
// Сервисная функция, которая возвращает true, если есть
// подмножество arr [] с солнцем, равным данной сумме

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]);

}

  
// Возвращает true, если arr [] можно разбить на два
// подмножества равной суммы, иначе ложь

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[] = {3, 1, 5, 9, 12};

  int n = 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");

  return 0;

}

Джава

// Рекурсивное решение Java для проблемы разбиения

import java.io.*;

  

class Partition

{

    // Сервисная функция, которая возвращает true, если есть

    // подмножество arr [] с солнцем, равным данной сумме

    static boolean 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]);

    }

  

    // Возвращает true, если arr [] можно разбить на два

    // подмножества равной суммы, иначе ложь

    static boolean findPartition (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);

    }

  

    / * Функция драйвера для проверки вышеуказанной функции * /

    public static void main (String[] args)

    {

  

        int arr[] = {3, 1, 5, 9, 12};

        int n = 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 [] с солнцем, равным заданной сумме

def isSubsetSum (arr, n, sum):

    # Базовые случаи

    if sum == 0:

        return True

    if n == 0 and sum != 0:

        return False

  

    # Если последний элемент больше суммы, то

    # игнорируй это

    if arr[n-1] > sum:

        return isSubsetSum (arr, n-1, sum)

  

    '' 'иначе, проверьте, может ли сумма быть получена любым из

    следующее

    (а) включая последний элемент

    (б) исключая последний элемент '' '

      

    return isSubsetSum (arr, n-1, sum) or isSubsetSum (arr, n-1, sum-arr[n-1])

  
# Возвращает true, если arr [] можно разбить на два
# подмножества равной суммы, иначе ложь

def findPartion (arr, n):

    # Рассчитать сумму элементов в массиве

    sum = 0

    for i in range(0, n):

        sum += arr[i]

    # Если сумма нечетная, не может быть двух подмножеств

    # с равной суммой

    if sum % 2 != 0:

        return false

  

    # Найти, есть ли подмножество с суммой, равной

    # половина от общей суммы

    return isSubsetSum (arr, n, sum // 2)

  
# Программа драйвера для проверки вышеуказанной функции

arr = [3, 1, 5, 9, 12]

n = len(arr)

if findPartion(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 # для проблемы разбиения

using System;

  

class GFG

{

    // Сервисная функция, которая возвращает true, если есть

    // подмножество arr [] с солнцем, равным данной сумме

    static 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]);

    }

  

    // Возвращает true, если arr [] можно разбить на два

    // подмножества равной суммы, иначе ложь

    static bool findPartition (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);

    }

  

    // Функция драйвера

    public static void Main ()

    {

  

        int []arr = {3, 1, 5, 9, 12};

        int n = 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 [] с солнцем, равным данной сумме

function isSubsetSum ($arr, $n, $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]); 

}  

  
// Возвращает true, если arr [] может быть разделен
// в двух подмножествах равной суммы, в противном случае ложь

function findPartiion ($arr, $n

    // Рассчитать сумму элементов

    // в массиве

    $sum = 0; 

    for ($i = 0; $i < $n; $i++) 

    $sum += $arr[$i]; 

  

    // Если сумма нечетная, не может быть

    // два подмножества с равной суммой

    if ($sum % 2 != 0) 

    return false; 

  

    // Найти, есть ли подмножество с суммой

    // равно половине общей суммы

    return isSubsetSum ($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>

using namespace std;

  
// Возвращает true, если arr [] может быть разделен
// в двух подмножествах равной суммы, в противном случае ложь

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][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];

    соиЬ << епсИ;

    } * /

      

    return part[sum / 2][n]; 

  
// Код драйвера

int main() 

    int arr[] = {3, 1, 1, 2, 2, 1}; 

    int n = 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"

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Программа C на основе динамического программирования для разделения задачи
#include <stdio.h>

  
// Возвращает true, если arr [] можно разбить на два подмножества
// равная сумма, иначе ложь

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][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]);

       Е ( "/ п");

     } * / 

       

     return part[sum/2][n];

}     

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

  int arr[] = {3, 1, 1, 2, 2, 1};

  int n = 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();

  return 0;

}

Джава

// Java-программа на основе динамического программирования для решения проблемы секционирования

import java.io.*;

  

class Partition {

  

    // Возвращает true, если arr [] можно разбить на два подмножества

    // равная сумма, иначе ложь

    static boolean findPartition (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;

  

        boolean part[][]=new boolean[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]);

            Е ( "/ п");

        } * /

  

        return part[sum/2][n];

    }

  

    / * Функция драйвера для проверки вышеуказанной функции * /

    public static void main (String[] args)

    {

        int arr[] = {3, 1, 1, 2, 2,1};

        int n = 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 [] может быть
# разбит на два подмножества
# равная сумма, иначе ложь

def findPartition(arr, n):

    sum = 0

    i, j = 0, 0

      

    # вычислить сумму всех элементов

    for i in range(n):

        sum += arr[i]

      

    if sum % 2 != 0:

        return false

      

    part = [[ True for i in range(n + 1)] 

                   for j in range(sum // 2 + 1)]

      

    # инициализировать верхнюю строку как true

    for i in range(0, n + 1):

        part[0][i] = True

          

    # инициализировать крайний левый столбец,

    # кроме части [0] [0], как 0

    for i in range(1, sum // 2 + 1):

        part[i][0] = False

      

    # заполнить таблицу разделов в

    # снизу вверх

    for i in range(1, sum // 2 + 1):

          

        for j in range(1, n + 1):

            part[i][j] = part[i][j - 1]

              

            if i >= arr[j - 1]:

                part[i][j] = (part[i][j] or 

                              part[i - arr[j - 1]][j - 1])

          

    return part[sum // 2][n]

      
Код водителя

arr = [3, 1, 1, 2, 2, 1]

n = len(arr)

if findPartition(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 # на основе динамического программирования
// для проблемы с разделом

using System;

  

class GFG {

      

    // Возвращает true, если arr [] может быть разделен

    // в двух подмножествах равной суммы, в противном случае

    // ложный

    static bool findPartition (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=new bool[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]);

            Е ( "/ п");

        } * /

  

        return part[sum / 2, n];

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main ()

    {

        int []arr = {3, 1, 1, 2, 2,1};

        int n = 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)
Обратите внимание, что это решение не подходит для массивов с большой суммой.

Ссылки:
http://en.wikipedia.org/wiki/Partition_problem

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проблема с разделами | DP-18

0.00 (0%) 0 votes