你好,我正在处理以下问题。
给定一个大小为M x N的矩阵,其中包含正系数。目标是选择P列,使得所得到的M x P矩阵中每一行元素的和最小化。例如,如果M = 3,N = 5,P = 2,矩阵如下:
a11 a12 a13 a14 a15
a21 a22 a23 a24 a25
a31 a32 a33`a34 a35
最优解是选择第2列和第4列,所得到的矩阵如下:
a12 a14
a22 a24
a32 a34
在所有选择P列的情况下,max{a12 + a14, a22 + a24, a32 + a34}的值最小。
虽然有(N over P)种解决方案,但可以实现一种简单的指数算法来解决这个问题,但是否有更快的多项式时间解决方案呢?
或者,如果没有,有人能够确定证明这是一个NP难问题吗?您是否知道任何类似的NP难问题可能会被归约到此问题?