Получение ошибки сегментации с проблемой подмножества dp - PullRequest
Новая
       9

Получение ошибки сегментации с проблемой подмножества dp

0 голосов
/ 18 февраля 2019

Учитывая набор чисел, проверьте, можно ли его разбить на два подмножества, чтобы сумма элементов в обоих подмножествах была одинаковой или нет. Я получаю ошибку сегментации в C ++ (g ++ 5.4) с этой проблемой.Здесь я отправил свое решение на C ++

https://practice.geeksforgeeks.org/problems/subset-sum-problem/0

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

Я реализовал приведенную ниже логику с динамическим программированием

Пусть dp [i] [j] обозначаетда или нет, возможно ли сформировать подмножество с суммой j с элементами в диапазоне [0, i] (включая оба), где i - это индекс на основе 0.Я не сделал ничего нового с этой традиционной проблемой.Но я получаю ошибку сегментации.Программа дает правильный вывод для небольших тестовых случаев.Какую ошибку я совершил

Я не использовал никаких комментариев, потому что я не сделал ничего нового.Надеюсь, это понятно. 

#include <iostream>
#include <bits/stdc++.h>
#include<cstdio>
#define ll long long int
using namespace std;


bool isVowel(char c){
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

bool isLower(char c){
    return 97 <= c && c <= 122;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << setprecision(10);

    ll t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        ll a[n];
        ll sum = 0;

        for (ll i = 0; i < n; i++) {
            cin >> a[i];
            sum += a[i];
        }

        if (sum % 2) {
            cout << "NO" << '\n';
            continue;
        }

        sum /= 2;
        ll dp[n][sum + 1];
        for (ll i = 0; i < n; i++) {
            for(ll j = 0; j < sum + 1; j++) {
                dp[i][j] = 0;
            }
        }

        for (ll i = 0; i < n; i++) {
            dp[i][a[i]] = 1;
            dp[i][0] = 1;
        }


        for (ll i = 1; i < n; i++) {
            for (ll j = 1; j < sum + 1; j++){
                if (j - a[i] > 0) {
                    dp[i][j] = dp[i - 1][j - a[i]];
                }

                dp[i][j] |= dp[i - 1][j];
            }
        }

        cout << (dp[n - 1][sum] ? "YES" : "NO") << '\n';

    }
}

1 Ответ

0 голосов
/ 19 февраля 2019

Ошибка сегментации происходит из-за 

ll dp[n][sum + 1];

Даже если ограничения говорят 1 <= N <= 100, 0 <= arr [i] <= 1000 </strong>, тестИспользуемые случаи, вероятно, намного больше, поэтому ll dp [n] [sum + 1] в конечном итоге потребует серьезной стековой памяти, используйте 

bool dp[n][sum + 1];

Это должно работать нормально.

В примечании, не используйте случайным образом, используйте их в соответствии с ограничениями.

...