arrays - 数组所有可能的组合

Question

我试图找到数组的所有可能组合。我找不到类似的问题所以我在这里问。

假设我有数组 A 和 N ，整数 T 作为输入，我需要找到满足以下不等式的数组 S 的所有可能组合。

---

输入:A(a1,a2,...,ak), N(n1,n2,...,nk), int T

输出:S(s1,s2,....sk)

受限于:

总和 ( si*ai ) <= T

和

对于每个 i: si<= ni

---

有什么想法吗？你如何实现它？我将使用 C++ 来实现它。

Answer 1

会有无解、无限多解、有限解的情况。

首先定义SUM(X,Y) = x_1*y_1 + x_2*y_2 + ... + x_k*y_k .

如果SUM(A,N) <= T然后 N是一个解决方案。

接下来，让Ni = (n_1, n_2, ..., [n_i]-1, ..., n_k) .如果SUM(A,Ni) < SUM(A,N)对于任何 i来自 1至 k那么就有无穷多个解。我们无法枚举它们，我们已经完成了。

否则，如果N不是解决方案，则没有解决方案，我们就完成了。

最后，如果上述两种情况都不成立，则解数有限。要枚举它们，请从 i=1 迭代至 k再次持有所有其他n常数，保持递减n_i按一个得到Ni'并检查是否 SUM(A,Ni') <= T .跟踪每个 n 的这些范围因为这些将是每个 n 的最大范围可以独立于其他人而变化，并且仍然(可能)给出解决方案。

最后，遍历所有 n 的笛卡尔积-确定范围并检查每个组合是否是解决方案。

我可能仍然遗漏了一些极端情况，但我相信这基本上是一个正确的解决方案。