寻找满足阈值要求的乘积背包问题最优解（含均衡权重偏好）

问题定义 #

输入：阈值T，条目列表L = [e₁, e₂, ..., eₙ]，每个条目eᵢ（1 ≤ i ≤ n）有最大权重wMaxᵢ和固定最小权重wMinᵢ = 1（wMaxᵢ ≥ wMinᵢ）。

输出：为每个条目选择权重wᵢ，满足：

• 1 ≤ wᵢ ≤ wMaxᵢ
• 所有权重的乘积W > T
• W尽可能小；若无法找到最小W，需满足W ∈ O(T)（即W < k*T，k为常数）
• 优先级：满足线性约束的前提下，优先选择wᵢ分布均衡的解（比如更倾向[2,2,2,2...]而非[4,1,4,1,...]），该优先级高于寻找最小W。

说明 #

• 所有数值均为整数
• 所有wMaxᵢ的乘积W_max远大于T

已尝试的方法 #

• 浮点数近似：为每个条目设置权重为ceil(logₙ(T))，但因wMax分布不均，该方法无效。
• 查阅乘积背包问题文献，但现有研究多聚焦于最大化权重，不确定该问题能否归约为背包问题（阈值处理与乘积运算存在难点）。
• 最终采用暴力方法：迭代均匀增加权重直至乘积超过T。

示例数据 #

• 条目：[e₁, e₂, e₃, e₄]
• 对应wMax：[3,3,2,5]
• 阈值T = 15

最接近阈值的解：

• [1, 3, 1, 5]（乘积15，注：需满足W>T，该解仅作参考）
• [3, 1, 1, 5]（乘积15，同上）

均衡性优先的近似解：

• [2, 2, 2, 2]（乘积16，满足W>T，且权重分布更均衡）

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