ones-and-zeroes.md

Ones and Zeroes

Apr 5, 2021 · 4 min read

Дан массив строк состоящих только из 0 и 1 и два числа m and n.

Нужно найти подмножество строк максимальной длины так, что в них содержится не более m нулей и n единиц.

Подмножество — значит можно брать любые элементы (строки) множества в любом порядке.

Пример.

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3

В этих строках {“10”, “0001”, “1”, “0”} содержится 3 единицы и 5 нулей. Подходит по условию, вернуть в ответе нужно 4.

Больше ни одна строка не подходит, потому что будет превышено количество доступных нулей.

Задача на LeetCode.

Решение #

Начем с самого простого — брутфорса, то есть перебора всех подмножеств. Какие ограничения в задаче? Строк не больше 600. В худшем случае, это… 2^600. Такое себе.

А что если жадный алгоритм? Нам нужно набрать как можно больше строк. Надо брать такие, в которых как можно меньше нулей и единиц, чтобы экономить доступные.

Идея хорошая, и на примере из условия работает. Однако, давайте рассмотрим такой контр-пример.

["111","1000","1000","1000"]
9
3

Взяв первую строку в ответ, мы израсходовали все доступные единицы, и дальше двигаться нельзя.

Выгоднее было пропустить первую строку и тогда можно взять следующие три, как раз получится 3 единицы и 9 нулей.

Как только я рассмотрел этот пример, мне сразу вспомнилась задача про максимальный профит в расписании задач.

Идея была в том, чтобы проверять две ветки: либо берём текущую задачу в расписание и ищем следующий доступный слот, либо не берём текущую задачу вовсе и начинаем поиск со следующей.

А это ведь то же самое!

Мы можем либо взять текущую строку, тем самым как-то потратив бюджет. Либо не брать текущую строку, сэкономив бюджет в надежде, что брать следующую строку окажется выгоднее.

    /**
     * Функция обхода возможных вариантов в глубину.
     * Принимает индекс массива откуда начинать поиск,
     * а так же доступный бюджет нулей и единиц
     */
    function dfs(from, _0sLimit, _1sLimit) {
        // от строки нам нужна просто пара чисел,
        // допустим, что мы преобразовали все строки
        const [_0s, _1s] = strs[from];
    
        // далее есть два варианта:
        return Math.max(
            // - брать текущую строку и тратить бюджет
            1 + dfs(from + 1, _0sLimit - _0s, _1sLimit - _1s),
            // - не брать текущую строку и экономить
            dfs(from + 1, _0sLimit, _1sLimit)
        );
    }

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

• потратили весь бюджет;
• дошли до конца массива.

function dfs(from, _0sLimit, _1sLimit) {
+   // потратили бюджет — вернём минус бесконечность,
+   // чтобы скомпенсировать +1 и этот результат точно
+   // отсеялся через Math.max 
+   if (_0sLimit < 0 || _1sLimit < 0) {
+       return -Infinity;
+   }
+   // дошли до конца массива, проверять нечего
+   if (from === strs.length) {
+       return 0;
+   }
    const [_0s, _1s] = strs[from];

    return Math.max(
        1 + dfs(from + 1, _0sLimit - _0s, _1sLimit - _1s),
        dfs(from + 1, _0sLimit, _1sLimit)
    );
}

Сложность однако по-прежнему O(2^K), где K количество строк. Как быть?

Здесь на помощь приходит динамическое программирование, или мемоизация. Вместо того, чтобы честно ходить по всему дереву возможных вариантов будем кешировать результаты.

Полученная функция — чистая, зависит от трёх аргументов и всё. Можно получить ключ от трёх аргументов, по которому класть результаты в кеш.

Итак, как же вкручивать кеш?

function dfs(from, _0sLimit, _1sLimit) {
    if (_0sLimit < 0 || _1sLimit < 0) {
        return -Infinity;
    }
    if (from === strs.length) {
        return 0;
    }
+   const key = `${from},${_0sLimit},${_1sLimit}`;
+   if (dp[key]) {
+       return dp[key];
+   }
    const [_0s, _1s] = strs[from];

+   dp[key] = Math.max(
-   return Math.max(
        1 + dfs(from + 1, _0sLimit - _0s, _1sLimit - _1s),
        dfs(from + 1, _0sLimit, _1sLimit)
    );
+   return dp[key];
}

Как это улучшит сложность?

O(K * M * N) — оценка на количество возможных сочетаний аргументов функции, значит и вызовов мы больше не сделаем. Подходит для оценки по времени алгоритмы, да и по памяти — потому что результаты надо хранить.

Всё вместе.

    /**
     * @param {string[]} strs
     * @param {number} m
     * @param {number} n
     * @return {number}
     */
    var findMaxForm = function(strs, m, n) {
        const LEN = strs.length;
        const dp = Object.create(null);
        strs = strs.map(count0sAnd1s);
    
        function count0sAnd1s(s) {
            let _0s = 0;
            let _1s = 0;
            for (let i = 0; i < s.length; i++) {
                if (s[i] === '0') _0s++;
                if (s[i] === '1') _1s++;
            }
            return [_0s, _1s];
        }
        function dfs(from, _0sLimit, _1sLimit) {
            if (_0sLimit < 0 || _1sLimit < 0) {
              return -Infinity;
            }
            if (from === LEN) {
              return 0;
            }
            const key = `${from},${_0sLimit},${_1sLimit}`;
            if (dp[key]) {
              return dp[key];
            }
            const [_0s, _1s] = strs[from];
            dp[key] = Math.max(
              1 + dfs(from + 1, _0sLimit - _0s, _1sLimit - _1s),
              dfs(from + 1, _0sLimit, _1sLimit)
            );
            return dp[key];
        }
        return dfs(0, m, n);
    };

Можно слегка ускориться на создании строк, и завести трехмерный массив для кеша.

Не смотря на то, что задача сдаётся, как видно из процентов выше — решение где-то в хвосте.

Есть другой вариант решения этой задачи, основанный на задаче оптимальной упаковки. Хотя сложность, по идее, та же, работает на практике значительно быстрее.

Данное решение мне всё равно нравится больше, потому что понятнее.

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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