矩阵每列选值组合相乘求最大乘积及对应行索引的实现咨询

现有如下3行10列的数值矩阵，要求从每列中选取1个元素，将所有选中元素相乘，找到所有组合中的最大乘积值，同时输出10列各自选中元素对应的行索引。

场景1：矩阵所有元素均为正数 #

因为乘法对正数的单调性，每列独立选择最大值相乘的结果就是全局最大乘积，不需要枚举所有组合，时间复杂度仅为O(行数×列数)，同时可以直接记录每列最大值对应的行索引。
示例代码：

import numpy as np

# 构造矩阵，行索引从0开始对应原表的1/2/3行，也可以直接用1开头的索引
matrix = np.array([
    [0.1, 0.1, 0.1, 0.2, 0.2, 0.2, 0.7, 0.7, 0.4, 0.7],
    [0.6, 0.6, 0.6, 0.1, 0.1, 0.1, 0.1, 0.1, 0.5, 0.1],
    [0.3, 0.3, 0.3, 0.7, 0.7, 0.7, 0.2, 0.2, 0.1, 0.2]
])

# 每列最大值对应的行索引（+1转成原表1开头的行号）
max_row_indices = np.argmax(matrix, axis=0) + 1
# 计算最大乘积
max_product = np.prod(np.max(matrix, axis=0))

print("最大乘积：", max_product)
print("各列对应行索引：", max_row_indices.tolist())

输出结果：

最大乘积： 0.0074071616
各列对应行索引： [2, 2, 2, 3, 3, 3, 1, 1, 2, 1]

场景2：矩阵存在负数/零的通用情况 #

负数相乘可能会让小值变大，需要用动态规划记录到当前列为止，选每行元素时的最大/最小乘积，同时维护路径回溯表，最后反向追溯得到完整的行索引序列。
示例代码：

import numpy as np

matrix = np.array([
    [0.1, 0.1, 0.1, 0.2, 0.2, 0.2, 0.7, 0.7, 0.4, 0.7],
    [0.6, 0.6, 0.6, 0.1, 0.1, 0.1, 0.1, 0.1, 0.5, 0.1],
    [0.3, 0.3, 0.3, 0.7, 0.7, 0.7, 0.2, 0.2, 0.1, 0.2]
])
row_cnt, col_cnt = matrix.shape

# 初始化dp表和路径表
dp_max = matrix[:, 0].copy()
dp_min = matrix[:, 0].copy()
# path[i][j]表示第j列选第i行时，上一列选的行号
path = np.zeros((row_cnt, col_cnt), dtype=int)

for j in range(1, col_cnt):
    temp_max = dp_max.copy()
    temp_min = dp_min.copy()
    for i in range(row_cnt):
        # 计算当前选第i行第j列的所有可能值
        candidates = [temp_max[k] * matrix[i][j] for k in range(row_cnt)] + [temp_min[k] * matrix[i][j] for k in range(row_cnt)]
        dp_max[i] = max(candidates)
        dp_min[i] = min(candidates)
        # 记录最优来源的行号
        path[i][j] = np.argmax([temp_max[k] * matrix[i][j] for k in range(row_cnt)] + [temp_min[k] * matrix[i][j] for k in range(row_cnt)]) % row_cnt

# 找最后一列的最大乘积对应的行
last_row = np.argmax(dp_max)
max_product = dp_max[last_row]
# 回溯路径
res_indices = [last_row + 1]
current_row = last_row
for j in range(col_cnt-1, 0, -1):
    current_row = path[current_row][j]
    res_indices.append(current_row + 1)
# 反转得到从第一列到最后一列的行索引
res_indices = res_indices[::-1]

print("最大乘积：", max_product)
print("各列对应行索引：", res_indices)

暴力法优化（仅适合列数较少的场景） #

如果一定要用枚举所有组合的方案，可以用迭代器生成所有行索引组合，计算乘积的同时同步记录最大值对应的索引，不需要先生成全量路径矩阵：

from itertools import product
import numpy as np

matrix = np.array([
    [0.1, 0.1, 0.1, 0.2, 0.2, 0.2, 0.7, 0.7, 0.4, 0.7],
    [0.6, 0.6, 0.6, 0.1, 0.1, 0.1, 0.1, 0.1, 0.5, 0.1],
    [0.3, 0.3, 0.3, 0.7, 0.7, 0.7, 0.2, 0.2, 0.1, 0.2]
])
row_cnt, col_cnt = matrix.shape

max_product = 0
best_path = None
# 生成所有行索引组合，每个元素是对应列选的行号
for path in product(range(row_cnt), repeat=col_cnt):
    current_prod = np.prod([matrix[path[i], i] for i in range(col_cnt)])
    if current_prod > max_product:
        max_product = current_prod
        best_path = [x+1 for x in path]

print("最大乘积：", max_product)
print("各列对应行索引：", best_path)

内容的提问来源于stack exchange，提问作者Rahil Vora