arrays - 查找列总和至少达到目标的最小行集

Question

我正在尝试编写一个算法来打印以下问题的解决方案：

给定一个目标数组 T = [t ₁ , t ₂ , ... t _n ] 和一组列表 S = { A = [a ₁ , a ₂ , ... a _n ], B = [b ₁ , b ₂ , ... b _n ], ... X = [x ₁ , x ₂ , ... x _n ] }，满足 i 之和的条件的具有最低基数的 S 子集是什么子集中每个数组的^{第 th}项至少为 t _i ?

例子：

T = [2, 3, 1]

S = {[0, 1, 2], [1, 0, 1], [2, 2, 0]}

满足上述条件的具有最低基数的子集就是集合{[0, 1, 2], [2, 2, 0]}。将每个数组的第 i^项之和表示为[2, 3, 2]，可以看到每个第 i^项之和都大于或等于 T 的第 i^项。

我查看了其他子集和问题，但无法提出一种有效的算法来解决这个问题。

标签： arraysalgorithmmathsubset-sum