Почему мой подход к сумме подмножества неверен?

Question

Я новичок в программировании Dynami c и придумал свой (очевидно неправильный) подход к проблеме подмножества суммы. Хотелось бы узнать, почему мой подход неверен. В частности, мне любопытно, верна ли основная идея вообще, или я должен просто придерживаться обычного подхода к сумме подмножества см. Yt .

Проблема: Учитывая массив чисел, найдите в нем 2 подмножества, которые имеют одинаковую сумму. Эта проблема немного изменена по сравнению с обычной проблемой суммы подмножеств.

Пример: [1,5,5,9] можно разделить на [1,9] и [5,5].

Идея:

   1  5  5  9
   0  5  5  9
1  1  6  6  10
5  6  5  6  10
5  6  10 10 10
9  6  10 10 10

Вместо того, чтобы отслеживать, какие элементы я беру, а какие нет (как обычно), я хотел бы отслеживать сумму. Идея состоит в том, чтобы найти сумму предыдущих элементов в mem[i-1][j] (один над текущей позицией). Если это значение + текущее значение меньше или равно половине общей суммы (в данном случае 20), мы добавляем текущее значение к сумме. В противном случае мы просто берем предыдущее значение и игнорируем текущее значение.

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

В этом примере алгоритм завершится, когда увидит первые 10.

Реализация:

Играйте с кодом

bool has_solution(std::vector<int> &v) {
    const long long sum = accumulate(v.begin(), v.end(), 0);
    long long mem[v.size() + 1][v.size()];
    for (int j = 0; j < v.size(); ++j) {
        mem[0][j] = v.at(j);
    }
    mem[0][0] = 0;
    for(int i = 1; i < v.size(); ++i) {
        for (int j = 0; j < v.size(); ++j) {
            if (i - 1 == j) {
                mem[i][j] = v.at(i - 1);
            } else {
                const long long new_sum = mem[i - 1][j] + v.at(i - 1) ;
                if (new_sum <= sum - new_sum) {
                    mem[i][j] = new_sum;
                } else {
                    mem[i][j] = mem[i - 1][j];
                }
            }
            if (mem[i][j] * 2 == sum) {
                return true;
            }
        }
    }
    return false;
}

Алгоритм дает неверное решение для ввода [987, 856, 743, 491, 227, 365, 859, 936, 432, 551, 437, 228, 275, 407, 474]. Он должен возвращать истину, но возвращает ложь, согласно site .

Answer 1

Помимо проблемы нестандартных массивов переменной длины (см. Комментарий Blastfurnace ), ваша концепция не может работать.

Недостаток в том, что ваш код не учитывает возможность того, что два или более небольших значения должны быть пропущены, чтобы найти решение. (Обратите внимание также, что код и таблица, которую вы показали, не совпадают. Код никогда не выполняет строку 1 1 6 6 10).

Например, рассмотрим последовательность:

{4, 1, 6, 3, 4}

допустимы только разделы {4, 1, 4} и {6, 3}. Этот раздел требует пропуска двух небольших записей для обоих разделов, что не поддерживается.

Выполнение выглядит так:

  | 4   1   6    3   4
--+-------------------
4 |(0)  1   6    3   4
1 | 1  (1)  7    4   5
6 | 7   7  (7)   4   5 
3 | 7   7   7   (7)  8
4 | 7   7   7    7  (8)

Каждый столбец имеет свою проблему.

1. (С 4) пропускает первые 4, поэтому отказывается от подмножества {4, 1, 4}. Таким образом, он должен пропустить 1, но поскольку он добавляет его, этот столбец не будет работать.
2. (с 1) добавляет 1, поэтому его можно расширить только до {4, 1, 4}. Таким образом, он должен пропустить 6, но в конце добавляется, что ...
3. (с 6) добавляет 6, поэтому его можно расширить только до {4, 1, 4}, затем он добавляет 1, что является ХОРОШО. Но затем он добавляет 3, так как он достаточно мал (сумма 4 + 1 + 3 == 8). Но 3 он должен был его пропустить.
4. (С 3) добавляет 3+1+4 <9, что принимается кодом, но не приводит к действительному набору. </li>
5. ( С 4) добавляет 4+1+3 <9, как и выше. </li>

Если вы хотите использовать динамическое программирование c, вы должны перейти по ссылке , которую вы разместили . Для этого вам понадобится vector<bool> с элементами sum(v) / 2 + 1, инициализируйте его с помощью true для первого элемента и false для всех остальных. Вы можете сделать это, используя только один vector, поскольку вас интересует только , есть ли какое-либо решение, а не возвращать его.

Ваша сложность будет O (sum ( v) * v.size ()), что может быть слишком большим, если значения большие.

Если значения большие, вы можете вместо этого использовать std::unordered_set<int>, чтобы кодировать то же самое, что и выше vector<bool>, но редко. Сложность рассуждать труднее. В худшем случае каждое подмножество имеет разную сумму (например, {1, 2, 4, 8, ..., 2 ^N-2 }, K >>> 2 ^N-1 }). Это сделает стоимость O (2 ^N ), где N = v.size (). Это лучше, чем первый алгоритм, который стоит O (K), что в данном случае намного хуже, чем O (2 ^N ).