Поиск максимальной дробной части суммы элементов матрицы

[kisupov]

Есть матрица $n \times m$, элементы которой - дробные числа из интервала $[0,1)$. Нужно из каждого столбца выбрать по одному элементу так, чтобы дробная часть их суммы оказалась максимальной.

Например,для матрицы

\[ \left( \begin{array}{cccc} 0.3 & 0.4 & 0.1 & 0.5 \\ 0.2 & 0.7 & 0.2 & 0.8 \\ 0.1 & 0.6 & 0.3 & 0.2 \end{array} \right) \]

одним из решений будет $(0.3, 0.7, 0.1, 0.8)$, так как дробная часть суммы этих элементов равна $0.9$.

Очевидное решение - полный перебор, потребует времени $O(n^m)$, что неприемлемо много. Имеются ли какие-нибудь более эффективные алгоритмы?

[mihaild]

Если число разрядов ограничено $k$ - то можно динамикой аналогично рюкзаку за $10^k \cdot mn$.
Еще к задаче сводится рюкзак для случая, когда общий вес предметов меньше удвоенной вместимости. Но непонятно, является ли такой его случай $NP$-трудным.