选择列的子集以最大化多于零的行数

Question

考虑一个具有

m < 10000

行和

n < 1000

列（包含 1 和 0）的矩阵。我需要选择

k <= n

列，以便包含多于零的行数最大（

k

是固定的）。

这个问题有算法吗（近似算法也可以）？

Answer 1

这是我对 JavaScript 的看法。我很乐意提供帮助。

function maxRowsWithMoreOnes(matrix, k) {
    const m = matrix.length;
    const n = matrix[0].length;

    // Initialize DP array
    const DP = new Array(m + 1).fill(0).map(() => new Array(k + 1).fill(0));

    // Dynamic programming step
    for (let t = 1; t <= n; t++) {
        let onesCount = 0;
        let zerosCount = 0;
        for (let i = 1; i <= m; i++) {
            if (matrix[i - 1][t - 1] === 1) {
                onesCount++;
            } else {
                zerosCount++;
            }
            for (let j = k; j >= 1; j--) {
                DP[i][j] = Math.max(DP[i][j], DP[i - 1][j]);
                if (j > 0) {
                    DP[i][j] = Math.max(DP[i][j], DP[i - 1][j - 1] + (onesCount > zerosCount ? 1 : 0));
                }
            }
        }
    }

    // Find the maximum value in the last row of DP
    let maxRows = 0;
    for (let j = 0; j <= k; j++) {
        maxRows = Math.max(maxRows, DP[m][j]);
    }

    return maxRows;
}

// Example usage:
const matrix = [
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 1, 0, 0],
    [0, 0, 1, 1]
];
const k = 2;
console.log(maxRowsWithMoreOnes(matrix, k)); // Output: 3