Проблема разбиения - поиск элементов множества с использованием минимальной памяти

Question

Мне нужно решить проблему с классическими c разделами, используя динамическое c программирование. У меня есть массив натуральных чисел в качестве входных данных, где n является числом целых чисел, а s является суммой этих целых чисел, и мне нужно найти минимальную разницу между двумя наборами, которые может быть построен с использованием элементов ввода. Мне также нужно вывести логический массив, называемый «владельцем», того же размера, что и входной массив, который предоставляет информацию, принадлежат ли элементы первому или второму оптимальному набору. Например, если i-тое значение в массиве владения равно true, то элемент i-тый входного массива принадлежит первому набору.

Моя программа находит минимальную разницу, используя подход снизу вверх. Задача требует, чтобы сложность памяти программы составляла θ ( s ), поэтому вместо использования двумерного массива размером n * s, как в классическом подходе, я использую только два строки этого массива. В первой строке я сохраняю предыдущую обработанную строку, чтобы заполнить вторую строку, основываясь на предыдущих решениях.

Проблема в том, что при такой оптимизации памяти я не уверен, как мне заполнить массив владения ,

Я знаю, что можно получить установленные элементы, используя возврат в массиве n * s. Однако из-за ограничений задачи я не могу использовать этот метод и понятия не имею, как эффективно построить таблицу владения.

Существует ли способ эффективно определить, какие элементы принадлежат к какому из этих двух оптимальных наборов , с ограничением сложности памяти θ ( s ) и сложности времени O (n * s) в восходящем подходе?

Мой текущий код в C#:

 public int SetsMinimum(int[] tab, out bool[] ownership)
 {
    int n = tab.Length;
    int sum = 0;
    foreach (int v in tab) sum += v;
    ownership = new bool[n];
    bool[,] dp = new bool[2, sum + 1];
    int min = sum;
    dp[0, 0] = true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= sum; j++)
        {
            dp[1,j] = dp[0,j];
            if (j - tab[i - 1]>=0)
            {
                dp[1, j] = dp[0, j - tab[i - 1]];
            }     
        }
        for(int j=0;j<sum;j++)
        {
            if (dp[1, j])
            {
                int cMin = Math.Abs((sum - j) - j);
                if (min>cMin)
                {
                    min = cMin;
                }
            }    
            dp[0, j] = dp[1, j];
        }
    }
    return min;
}

Answer 1

Вчера я нашел решение:

1. Инициализируйте другой массив из sum+1 элементов и заполните его нулями.
2. При переборе по массиву dp сохраните в предыдущем индексе массива первый элемент, который позволил достичь каждой суммы. Например, для {4,3,2} вы можете получить сумму 7, когда используете второй элемент, и вы можете получить сумму 4 с первым элементом.
3. Получив минимальную разницу, выберите одну из оптимальных сумм наборов. либо (sum-min)/2, либо sum-((sum-min)/2).
4. Перейти к сумме в массиве индекса, установить для массива владения значение true в индексе, указанном в массиве индекса, а затем вычесть элемент из суммы. Повторяйте до тех пор, пока ваша сумма не станет равной нулю.

Этот подход будет выбирать только необходимые элементы для построения любого из наборов sum, и он будет работать через O (n * s) время с индексный массив может быть заполнен во время подхода снизу вверх.

Answer 2

Вы можете написать функцию, которая запускается в памяти O(s), которая запускает DP один раз и находит ближайшую целевую сумму.

Вы можете написать функцию, которая запускается в памяти O(s), которая запускает DP один раз, и выясняет, должно ли последнее значение быть истинным или ложным в массиве владения, чтобы достичь этой целевой суммы.

Несколько раз запустить вторую функцию, чтобы отобрать каждого члена массива владения от конца до фронта.

Это займет память O(s) и время O(s * n^2). (Потому что вы запускаете n DP.) В отличие от обычного подхода DP, который занимает память O(s * n) и время O(s * n).