Найти покрытие столбцов строками

From

Max Alekseyev (2:5015/60)

To

Rustam Ramazanov

Date

2002-10-23T13:57:20Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Rustam !

Replying to a message of Rustam Ramazanov to Eugeny Tertishny:

 ET>> Есть матрица 16х14, несимметричная. Заполненная
 ET>> нулями и единицами. Необходимо
 ET>> найти минимальное количество строк, таких чтобы
 ET>> хоть в одном столбце была 1.
 ET>> Считается, что такие строки в любом случае есть
 RR> Упрощает жизнь, но не является решающим фактором.

 ET>> Хочется сделать не используя пер**ор. 
 RR> А чем перебор плох? К тому же все перебирать не надо.
 RR> Можно сделать следующее:
 RR> 1. Берем строку в которой максимальное число единиц.
 RR> Запомним столбцы в которых стоят единицы.
 RR> 2. В оставшихся строках в запомненных столбцах ставим 0.
 RR> 3. Переходим в п.1. Работа алгоритма заканчивается либо если во всех 
 RR> строках остаются только нули, либо если перебрали все строки (это тот 
 RR> самый худший вариант).

Эта эвристика не дает минимальное решение. Минимальное решение может не содержать строку, с максимальным числом единиц - например:

111100
000010
000001
001110
110001

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)