Как оптимизировать поиск комбинации строк и столбцов в матрице?
=================================================================

 Дана матрица единиц и нолей. Надо выбрать в ней такую комбинацию столбцов и строк, чтобы максимизировать отношение числа клеток с "1" к числу клеток с "0". При этом чем больше строк и столбцов участвует, тем лучше.  
  

Например, тут строки (0,1,3) со столбцами (0,3,5) дают всего один "0" при восьми "1":
```
1 0 0 1 0 1
1 1 0 1 1 1
0 1 0 1 0 0
1 1 0 0 0 1
```
  
  

Как я понял, задача NP-полная, т.е. требуется полный перебор всех возможных сочетаний. Хочется находить такие максимальные выборки на довольно большом числе строк и столбцов: от тысяч до миллионов.  
  

Какие есть алгоритмы, оптимизирующие этот перебор?  
  

Как частный случай нужно искать сочетания вообще без единого "0". 

 Не тестировал, но как-то так:  

1. Считаем сумму всех значений матрицы N, а так же сумму для каждой строки и столбца M[] и соотношение 1 к 0 Z;  

2. Вычитаем из N минимальное значение среди M: N -= min(M).;  

3. "Убираем" строку или столбец соответсвующую min(M) из матрицы: вычитаем из каждого столбца или строки (соответственно) значения на пересечении и параллельно обновляем Z;  

4. Сравниваем Z с предыдущим значением. Если оно стало больше - вернуться к шагу 2. Если меньше - комбинация найдена (неудаленые строки и столбцы).