Рубрики

Количество способов разбить массив на K равных по сумме подмассивов

Для заданного целого числа K и массива arr [] из N целых чисел задача состоит в том, чтобы найти число способов разбить массив на K равных по сумме подмассивов ненулевой длины.

Примеры:

Input: arr[] = {0, 0, 0, 0}, K = 3
Output: 3
All possible ways are:
{{0}, {0}, {0, 0}}
{{0}, {0, 0}, {0}}
{{0, 0}, {0}, {0}}

Input: arr[] = {1, -1, 1, -1}, K = 2
Output: 1

Подход: эту проблему можно решить с помощью динамического программирования . Ниже будет наш алгоритм:

  1. Найдите сумму всех элементов массива и сохраните ее в переменной SUM .
    Прежде чем перейти к шагу 2, давайте попробуем разобраться в состояниях DP.
    Для этого представьте, как поместить столбцы для разделения массива на K равных частей. Итак, мы должны поставить K — 1 баров в общей сложности.
    Таким образом, наши состояния dp будут содержать 2 члена.
    • i — индекс элемента, на котором мы сейчас находимся.
    • ck — количество баров, которые мы уже вставили + 1.

    dp [i] [ck] можно определить как количество способов поместить оставшиеся бары в массив так, чтобы он был разделен на K равных половин. Теперь перейдем к шагу 2 нашего алгоритма.

  2. Вызовите рекурсивную функцию с i = 0 и ck = 1, и отношение рекуррентности будет:

    Case 1: sum upto index i equals ((SUM)/k)* ck
    dp[i][ck] = dp[i+1][ck] + dp[i+1][ck+1]
    Case 2: sum upto index not i equals ((SUM)/k)* ck
    dp[i][ck] = dp[i+1][ck]

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>
#define max_size 20
#define max_k 20

using namespace std;

  
// Массив для хранения состояний DP

int dp[max_size][max_k];

  
// Массив, чтобы проверить, если
// состояние было решено раньше

bool v[max_size][max_k];

  
// Для хранения суммы
// элементы массива

int sum = 0;

  
// Функция для поиска суммы
// все элементы массива

void findSum(int arr[], int n)

{

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

        sum += arr[i];

}

  
// Функция для возврата количества способов

int cntWays(int arr[], int i, int ck,

            int k, int n, int curr_sum)

{

    // Если сумма не делится на k

    // ответ будет нулевым

    if (sum % k != 0)

        return 0;

    if (i != n and ck == k + 1)

        return 0;

  

    // Базовый вариант

    if (i == n) {

        if (ck == k + 1)

            return 1;

        else

            return 0;

    }

  

    // Чтобы проверить, если состояние

    // было решено ранее

    if (v[i][ck])

        return dp[i][ck];

  

    // Сумма всех чисел с начала

    // массива

    curr_sum += arr[i];

  

    // Установка текущего состояния как решено

    v[i][ck] = 1;

  

    // Рекуррентное отношение

    dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum);

    if (curr_sum == (sum / k) * ck)

        dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum);

  

    // Возвращаем разрешенное состояние

    return dp[i][ck];

}

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

int main()

{

    int arr[] = { 1, -1, 1, -1, 1, -1 };

    int n = sizeof(arr) / sizeof(int);

    int k = 2;

  

    // вызов функции для поиска

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

    findSum(arr, n);

  

    // Вывести количество способов

    cout << cntWays(arr, 0, 1, k, n, 0);

}

Джава

// Java реализация подхода

class GFG 

{

      

static int max_size= 20;

static int max_k =20;

  
// Массив для хранения состояний DP

static int [][]dp = new int[max_size][max_k];

  
// Массив, чтобы проверить, если
// состояние было решено раньше

static boolean [][]v = new boolean[max_size][max_k];

  
// Для хранения суммы
// элементы массива

static int sum = 0;

  
// Функция для поиска суммы
// все элементы массива

static void findSum(int arr[], int n)

{

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

        sum += arr[i];

}

  
// Функция для возврата количества способов

static int cntWays(int arr[], int i, int ck,

            int k, int n, int curr_sum)

{

    // Если сумма не делится на k

    // ответ будет нулевым

    if (sum % k != 0)

        return 0;

    if (i != n && ck == k + 1)

        return 0;

  

    // Базовый вариант

    if (i == n) 

    {

        if (ck == k + 1)

            return 1;

        else

            return 0;

    }

  

    // Чтобы проверить, если состояние

    // было решено ранее

    if (v[i][ck])

        return dp[i][ck];

  

    // Сумма всех чисел с начала

    // массива

    curr_sum += arr[i];

  

    // Установка текущего состояния как решено

    v[i][ck] = true;

  

    // Рекуррентное отношение

    dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum);

    if (curr_sum == (sum / k) * ck)

        dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum);

  

    // Возвращаем разрешенное состояние

    return dp[i][ck];

}

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

public static void main(String[] args)

{

    int arr[] = { 1, -1, 1, -1, 1, -1 };

    int n = arr.length;

    int k = 2;

  

    // вызов функции для поиска

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

    findSum(arr, n);

  

    // Вывести количество способов

    System.out.println(cntWays(arr, 0, 1, k, n, 0));

}
}

  
// Этот код предоставлен Принчи Сингхом

python3

# Python3 реализация подхода

import numpy as np

  

max_size = 20 

max_k = 20 

  

  
# Массив для хранения состояний DP

dp = np.zeros((max_size,max_k)); 

  
# Массив, чтобы проверить, если
# состояние было решено раньше

v = np.zeros((max_size,max_k)); 

  
# Для хранения суммы
# элементы массива

sum = 0

  
# Функция, чтобы найти сумму
# все элементы массива

def findSum(arr, n) : 

    global sum

    for i in range(n) :

        sum += arr[i]; 

  

  
# Функция для возврата количества способов

def cntWays(arr, i, ck, k, n,  curr_sum) : 

  

    # Если сумма не делится на k

    # ответ будет нулевым

    if (sum % k != 0) :

        return 0

    if (i != n and ck == k + 1) :

        return 0

  

    # Базовый вариант

    if (i == n) :

        if (ck == k + 1) :

            return 1

        else :

            return 0

  

    # Чтобы проверить, если состояние

    # был решен ранее

    if (v[i][ck]) :

        return dp[i][ck]; 

  

    # Сумма всех чисел с начала

    № массива

    curr_sum += arr[i]; 

  

    # Установка текущего состояния как решено

    v[i][ck] = 1

  

    # Рекуррентное отношение

    dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum); 

    if (curr_sum == (sum / k) * ck)  :

        dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum); 

  

    # Возвращение решенного состояния

    return dp[i][ck]; 

   

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

if __name__ == "__main__"

  

    arr = [ 1, -1, 1, -1, 1, -1 ]; 

    n = len(arr); 

    k = 2

  

    # Вызов функции, чтобы найти

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

    findSum(arr, n); 

  

    # Распечатать количество способов

    print(cntWays(arr, 0, 1, k, n, 0)); 

  

    # Этот код предоставлен AnkitRai01

C #

// C # реализация подхода

using System;     

      

class GFG 

{

      

static int max_size= 20;

static int max_k =20;

  
// Массив для хранения состояний DP

static int [,]dp = new int[max_size, max_k];

  
// Массив, чтобы проверить, если
// состояние было решено раньше

static Boolean [,]v = new Boolean[max_size, max_k];

  
// Для хранения суммы
// элементы массива

static int sum = 0;

  
// Функция для поиска суммы
// все элементы массива

static void findSum(int []arr, int n)

{

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

        sum += arr[i];

}

  
// Функция для возврата количества способов

static int cntWays(int []arr, int i, int ck,

            int k, int n, int curr_sum)

{

    // Если сумма не делится на k

    // ответ будет нулевым

    if (sum % k != 0)

        return 0;

    if (i != n && ck == k + 1)

        return 0;

  

    // Базовый вариант

    if (i == n) 

    {

        if (ck == k + 1)

            return 1;

        else

            return 0;

    }

  

    // Чтобы проверить, если состояние

    // было решено ранее

    if (v[i, ck])

        return dp[i, ck];

  

    // Сумма всех чисел с начала

    // массива

    curr_sum += arr[i];

  

    // Установка текущего состояния как решено

    v[i, ck] = true;

  

    // Рекуррентное отношение

    dp[i,ck] = cntWays(arr, i + 1, ck, k, n, curr_sum);

    if (curr_sum == (sum / k) * ck)

        dp[i, ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum);

  

    // Возвращаем разрешенное состояние

    return dp[i, ck];

}

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

public static void Main(String[] args)

{

    int []arr = { 1, -1, 1, -1, 1, -1 };

    int n = arr.Length;

    int k = 2;

  

    // вызов функции для поиска

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

    findSum(arr, n);

  

    // Вывести количество способов

    Console.WriteLine(cntWays(arr, 0, 1, k, n, 0));

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

2

Сложность времени: O (n * k)

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

Количество способов разбить массив на K равных по сумме подмассивов

0.00 (0%) 0 votes