Найдите максимальную сумму подмножества, образованную разделением любого подмножества массива на 2 части с равной суммой

Опубликовано: 7 Января, 2022

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

Примечание: нет необходимости разбивать весь массив, т. Е. Любой элемент может не входить ни в один из разделов.

Примеры:

Input: A = [1, 2, 3, 6]
Output: 6
Explanation: We have two disjoint subsets {1, 2, 3} and {6}, which have the same sum = 6
Input: A = [1, 2, 3, 4, 5, 6]
Output: 10
Explanation: We have two disjoint subsets {2, 3, 5} and {4, 6}, which have the same sum = 10.
Input: A = [1, 2]
Output: 0
Explanation: No subset can be partitioned into 2 disjoint subsets with identical sum

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход:
Вышеуказанная проблема может быть решена методом перебора с использованием рекурсии . У всех элементов есть три возможности. Либо он будет использоваться в разделе 1 или разделе 2, либо не будет включен ни в один из разделов. Мы выполним эти три операции с каждым элементом и перейдем к следующему элементу на каждом рекурсивном шаге.

Below is the implementation of the above approach:

C++

// CPP implementation for the
// above mentioned recursive approach
  
#include <bits/stdc++.h>
  
using namespace std;
  
// Function to find the maximum subset sum
int maxSum(int p0, int p1, int a[], int pos, int n)
{
    if (pos == n) {
        if (p0 == p1)
            return p0;
        else
            return 0;
    }
    // Ignore the current element
    int ans = maxSum(p0, p1, a, pos + 1, n);
  
    // including element in partition 1
    ans = max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n));
  
    // including element in partition 2
    ans = max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n));
    return ans;
}
  
// Driver code
int main()
{
    // size of the array
    int n = 4;
    int a[n] = { 1, 2, 3, 6 };
    cout << maxSum(0, 0, a, 0, n);
    return 0;
}

Java

// Java implementation for the
// above mentioned recursive approach
class GFG {
      
    // Function to find the maximum subset sum
    static int maxSum(int p0, int p1, int a[], int pos, int n)
    {
        if (pos == n) {
            if (p0 == p1)
                return p0;
            else
                return 0;
        }
  
        // Ignore the current element
        int ans = maxSum(p0, p1, a, pos + 1, n);
      
        // including element in partition 1
        ans = Math.max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n));
      
        // including element in partition 2
        ans = Math.max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n));
        return ans;
    }
      
    // Driver code
    public static void main (String[] args)
    {
        // size of the array
        int n = 4;
        int a[] = { 1, 2, 3, 6 };
        System.out.println(maxSum(0, 0, a, 0, n));
          
    }
}
  
// This code is contributed by AnkitRai01

Python3

# Python3 implementation for the
# above mentioned recursive approach
  
# Function to find the maximum subset sum
def maxSum(p0, p1, a, pos, n) :
  
    if (pos == n) :
        if (p0 == p1) :
            return p0;
        else :
            return 0;
      
    # Ignore the current element
    ans = maxSum(p0, p1, a, pos + 1, n);
  
    # including element in partition 1
    ans = max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n));
  
    # including element in partition 2
    ans = max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n));
      
    return ans;
  
# Driver code
if __name__ == "__main__" :
  
    # size of the array
    n = 4;
    a = [ 1, 2, 3, 6 ];
      
    print(maxSum(0, 0, a, 0, n));
  
# This code is contributed by AnkitRai01

C#

// C# implementation for the
// above mentioned recursive approach
  
using System;
  
public class GFG {
      
    // Function to find the maximum subset sum
    static int maxSum(int p0, int p1, int []a, int pos, int n)
    {
        if (pos == n) {
            if (p0 == p1)
                return p0;
            else
                return 0;
        }
  
        // Ignore the current element
        int ans = maxSum(p0, p1, a, pos + 1, n);
      
        // including element in partition 1
        ans = Math.Max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n));
      
        // including element in partition 2
        ans = Math.Max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n));
        return ans;
    }
      
    // Driver code
    public static void Main (string[] args)
    {
        // size of the array
        int n = 4;
        int []a = { 1, 2, 3, 6 };
        Console.WriteLine(maxSum(0, 0, a, 0, n));
          
    }
}
  
// This code is contributed by AnkitRai01

Output:

Сложность времени:

Эффективный подход:
Вышеупомянутый метод можно оптимизировать с помощью метода динамического программирования.

Мы определим наше состояние DP следующим образом:

dp[i][j] = Max sum of group g0 considering the first i elements such that,

the difference between the sum of g0 and g1 is (sum of all elements – j), where j is the difference.
So, the answer would be dp[n][sum]

Теперь мы можем столкнуться с тем, что разница между суммами отрицательна и находится в диапазоне [-sum, + sum], где сумма представляет собой сумму всех элементов. Минимальный и максимальный диапазоны, возникающие, когда одно из подмножеств пусто, а другое содержит все элементы. В связи с этим в состоянии DP мы определили j как (sum - diff). Таким образом, j будет варьироваться от [0, 2 * сумма].

Below is the implementation of the above approach:

C++

// CPP implementation for the above mentioned
// Dynamic Programming  approach
  
#include <bits/stdc++.h>
  
using namespace std;
  
// Function to find the maximum subset sum
int maxSum(int a[], int n)
{
    // sum of all elements
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += a[i];
  
    int limit = 2 * sum + 1;
  
    // bottom up lookup table;
    int dp[n + 1][limit];
  
    // initialising dp table with INT_MIN
    // where, INT_MIN means no solution
    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < limit; j++)
            dp[i][j] = INT_MIN;
    }
  
    // Case when diff is 0
    dp[0][sum] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < limit; j++) {
  
            // Putting ith element in g0
            if ((j - a[i - 1]) >= 0 && dp[i - 1][j - a[i - 1]] != INT_MIN)
  
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i - 1]]
                                             + a[i - 1]);
  
            // Putting ith element in g1
            if ((j + a[i - 1]) < limit && dp[i - 1][j + a[i - 1]] != INT_MIN)
  
                dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i - 1]]);
  
            // Ignoring ith element
            if (dp[i - 1][j] != INT_MIN)
  
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
        }
    }
  
    return dp[n][sum];
}
  
// Driver code
  
int main()
{
    int n = 4;
    int a[n] = { 1, 2, 3, 6 };
    cout << maxSum(a, n);
    return 0;
}

Java

// Java implementation for the above mentioned 
// Dynamic Programming approach 
class GFG {
      
    final static int INT_MIN = Integer.MIN_VALUE;
      
    // Function to find the maximum subset sum 
    static int maxSum(int a[], int n) 
    { 
        // sum of all elements 
        int sum = 0; 
        for (int i = 0; i < n; i++) 
            sum += a[i]; 
      
        int limit = 2 * sum + 1; 
      
        // bottom up lookup table; 
        int dp[][] = new int[n + 1][limit]; 
      
        // initialising dp table with INT_MIN 
        // where, INT_MIN means no solution 
        for (int i = 0; i < n + 1; i++) { 
            for (int j = 0; j < limit; j++) 
                dp[i][j] = INT_MIN; 
        } 
      
        // Case when diff is 0 
        dp[0][sum] = 0; 
        for (int i = 1; i <= n; i++) { 
            for (int j = 0; j < limit; j++) { 
      
                // Putting ith element in g0 
                if ((j - a[i - 1]) >= 0 && dp[i - 1][j - a[i - 1]] != INT_MIN) 
      
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - a[i - 1]] 
                                                + a[i - 1]); 
      
                // Putting ith element in g1 
                if ((j + a[i - 1]) < limit && dp[i - 1][j + a[i - 1]] != INT_MIN) 
      
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + a[i - 1]]); 
      
                // Ignoring ith element 
                if (dp[i - 1][j] != INT_MIN) 
      
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); 
            } 
        } 
      
        return dp[n][sum]; 
    } 
      
    // Driver code 
    public static void main (String[] args) 
    { 
        int n = 4; 
        int []a = { 1, 2, 3, 6 }; 
        System.out.println(maxSum(a, n)); 
    } 
}
  
// This code is contributed by AnkitRai01

C#

// C# implementation for the above mentioned 
// Dynamic Programming approach 
using System;
  
class GFG {
      
    static int INT_MIN = int.MinValue;
      
    // Function to find the maximum subset sum 
    static int maxSum(int []a, int n) 
    { 
        // sum of all elements 
        int sum = 0; 
        for (int i = 0; i < n; i++) 
            sum += a[i]; 
      
        int limit = 2 * sum + 1; 
      
        // bottom up lookup table; 
        int [,]dp = new int[n + 1,limit]; 
      
        // initialising dp table with INT_MIN 
        // where, INT_MIN means no solution 
        for (int i = 0; i < n + 1; i++) { 
            for (int j = 0; j < limit; j++) 
                dp[i,j] = INT_MIN; 
        } 
      
        // Case when diff is 0 
        dp[0,sum] = 0; 
        for (int i = 1; i <= n; i++) { 
            for (int j = 0; j < limit; j++) { 
      
                // Putting ith element in g0 
                if ((j - a[i - 1]) >= 0 && dp[i - 1,j - a[i - 1]] != INT_MIN) 
      
                    dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j - a[i - 1]] 
                                                + a[i - 1]); 
      
                // Putting ith element in g1 
                if ((j + a[i - 1]) < limit && dp[i - 1,j + a[i - 1]] != INT_MIN) 
      
                    dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j + a[i - 1]]); 
      
                // Ignoring ith element 
                if (dp[i - 1,j] != INT_MIN) 
      
                    dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j]); 
            } 
        } 
      
        return dp[n,sum]; 
    } 
      
    // Driver code 

            

                    
                                            Олимпиады по программированию
                                            Алгоритмы
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИРазница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022


    


        
            
                
                    
                        
                        < PROGLER >
                    
                
                
                    
                        Общее
                        
                        Контакты
                        Политика конфиденциальности
                    
                    
                        Обучение
                        Блог
                    
                
            
            
                © progler.ru 2024. Все права защищены.